doshin doshin - 1 year ago 58
Python Question

Error starting at n=8: "maximum recursion depth exceeded while calling a Python object"

I've seen some other similar topics, but I can't apply the solutions to fix the error given by the following code:

def mult_recursive(a,b):
if b == 1:
return a
return a + mult_recursive(a,b-1)

def factorial_recursive(n):
if n == 0:
return 1
elif n == 1:
return 1
return mult_recursive(n,factorial_recursive(n-1))

print (factorial_recursive(8))

It gives an error only if you choose an n >= 8. n in range 0 to 7 works fine.

Would be great if you could give an answer on why I get that error.
Thank you.

PS1: the code works fine for all numbers if you swap the mult_recursive fct's arguments
(n,factorial_recursive(n-1)) => (factorial_recursive(n - 1),n)

PS2: I know that there are simpler and better ways to compute factorials, but I just want to understand why that error starting at n=8.

Answer Source

You get that error because you've exceeded maximum recursion depth. What exactly you misunderstand? Go line by line and calculate the depth of calls you make. If you exceed max recursion depth, you're done. It seems that for n==8 you exceed it. For lowers you don't.

And that makes sense, since for n==8 you have factorial_recursive(n-1) == 5040 and thus mult_recursive(n, factorial_recursive(n-1)) does 5040 nested calls. This is definitely too much.

For n == 7 you only do 720 nested calls. By default max recursion is 1000 (might depend on your machine/python version) so there you go.