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))
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.
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
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.
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)))
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.
