Maximum recursion depth exceeded

2
votes

I receive the "max recursion depth exceeded" error.

#Defining an example function here
def f(x):
    return e**(-2*x)

#Command def simpsons(a,b):
c = (a+b)/2 return (b-a)/6*f(a)+4*f(c)+f(b)

#The Adaptive Simpson's formula
def adaptive_simpsons(a,b,tol,comparison):
    c = (a+b)/2
    left = simpsons(a,c)
    right = simpsons(c,b)
    if abs((left + right - comparison)/15) < tol:
        return (left + right - comparison)/15 + left + right
    else:
        return adaptive_simpsons(a,c,tol/2,left) + adaptive_simpsons(c,b,tol/2,right)

However, when I print: 

print adaptive_simpsons(a,b,tol, simpsons(a,b)),

I receive the error "maximum recursion depth exceeded"

Did I do anything wrong in my code, or is it really having to loop through this recursion formula many times? And, how would I fix this??

2
pythonrecursionmax
You can try to print the value of a, b, tol, and comparison at the beginning of adaptive_simpsons function to see where you would've gone wrong. If the code is correct, then, as others suggested, you need to change it into iterative instead of using recursion. - justhalf
Probably you shouldn't reduce the tol value? I guess that makes the function never reach the base case. - justhalf

2 Answers

2
votes

Python deplorably doesn't do tail call optimization. Hence you will have to serialize your recursion.

Also for TCO to work you will need to refactor your function (maybe adding an accumulator argument) to make it a tail call.

1
votes

You have an error in simpsons

def simpsons(a,b):   
    c = (a + b) / 2  #        V-here     and    here-V
    return abs((b - a) / 6) * (f(a) + 4 * f(c) + f(b))

Also, since you seem to be using Python2, you should have

from __future__ import division

at the start of the module