CODEWITHSUNDEEP
pythonpython-3.xrecursion
AfternoonTiger
AfternoonTiger

Reputation: 397

Approximate this equation using recursion 4 * (1 - (1 /3 ) + (1 / 5) - (1 / 7) + (1 / 9) - (1 / 11) ... )

How would I approximate the following equation using recursion? Here is an iterative approach:

def calculateFrac(num):
    result = 0
    for i in range(num):
        if i % 2 == 0:
            result = result + 1 / (2 * i + 1)
        else:
            result = result - 1 / (2 * i + 1)
        print(4 * result)

print(calculateFrac(10))

Upvotes: 0

Views: 478

Answers (3)

Olivier Melançon
Olivier Melançon

Reputation: 22304

First of all, you are also not returning the result. Here is a fixed version of your code.

def calculateFrac(num):
    result = 0
    for i in range(num):
        if i % 2 == 0:
            result = result + 1 / (2 * i + 1)
        else:
            result = result - 1 / (2 * i + 1)

    return result # return the result instead of printing it

print(calculateFrac(10)) # 0.7604599047323508

From there, the above code is perfectly fine.

Do not use recursion

Although, note that infinite series are better represented with a sum and a generator, not recursion. Especially in Python which does not optimize tail-recursion.

A recursive solution will be slower, use more memory and eventually hit the maximum recursion depth.

from itertools import islice, count

def seq():
    for n in count():
        yield (-1) ** n / (2 * n + 1)

print(sum(islice(seq(), 0, 10))) # 0.7604599047323508

Recursion practice

It seems you want to learn to use recursion. It is thus important you also identify problems where recursion is not necessary of efficient.

Recursion is usually more suited with problems that branch out at every iteration. That is problems of the form F(N) = F(N1) + F(N2) where N1 and N2 are subsets of N. A common example would be mergesort.

You can find many problem sets for such problems online.

Upvotes: 2

cdlane
cdlane

Reputation: 41872

I'm asking how would I solve this using recursion.

I don't disagree with @OlivierMelançon about this being a poor example for recursion. I'm providing just one possible implementation of the dreaded recursive solution:

def calculateFrac(num):
    if num < 1:
        return 0.0

    return calculateFrac(num - 1) + (2 * (num % 2) - 1) / (2 * num - 1)

print(calculateFrac(10))  # 0.7604599047323508 (put in the 4 *)

On my system the largest argument this can handle is 997 without explicitly expanding the call stack via sys.setrecursionlimit(). Using memoization techniques won't help. We can probably make a tail-recursive solution by doing something like:

def calculateFrac(num, sum=0.0):
    if num < 1:
        return sum

    return calculateFrac(num - 1, sum + (2 * (num % 2) - 1) / (2 * num - 1))

print(calculateFrac(10))  # 0.7604599047323506 (put in the 4 *)

Not that Python cares about such things. But if it did do tail-call optimization, then such as solution could be as fast as the iterative solutions and not have any stack limitations.

Upvotes: 0

MatBailie
MatBailie

Reputation: 86706

def calculateFraction(num):
  if (num > 0):
    return (-1)**(num) * 1/(num*2+1) + calculateFraction(num-1)
  else:
    return 1

print(4 * calculateFraction(10))

EDIT

Olivier's answer is extremely good, I wish I could upvote it several times.

In light of that I thought the OP may benefit from seeing a binary implementation of the above approach. That is to say, whenever recursing, send half the problem to one branch and the other half to another branch. (This means that, for example, asking for num=15 will result in a depth of 4 rather than a depth of 16.)

import inspect

def calculateFraction(num, end=0):
    result = 0
    depth = 'Depth({:d}){:s}>'.format(len(inspect.stack())-1, '='*(len(inspect.stack())-1)*2)

    # If there are an odd number of parts to calculate, do the highest one now
    if (((num-end+1)&1) == 1):
        result += ((-1)**(num)) / (num*2+1)
        print('{:s} Fraction part {:d} = {:f}'.format(depth, num, result))
        num-=1

    # If there are still any parts to calculate, do them recursively
    # (There must be an even number, as we did the odd one previously)
    # (That may leave 0 still to do, in which case the recursion is skipped)
    if (num > end):
        mid = ((num-end)>>1) + end

        # Do the upper half of the remaining parts
        print('{:s} Recursing to {:d},{:d}'.format(depth, num, mid+1))
        result += calculateFraction(num, mid+1)

        # Do the lower half of the remaining parts
        print('{:s} Recursing to {:d},{:d}'.format(depth, mid, end))
        result += calculateFraction(mid, end)

    return result

print('Result: {:f}'.format(4*calculateFraction(10)))

Upvotes: 2

Related Questions