0

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
    else:
        return a + mult_recursive(a,b-1)

def factorial_recursive(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        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.

doshin
  • 13
  • 5
  • Note that computing a simple multiplication recursively is definitly abusing recursion ... And that it is indeed what end up giving you that error. – jadsq Sep 17 '16 at 23:59
  • @Padraic Cunningham why is this a duplicate? this is a recursive function nested into a recursive function kind of situation – doshin Sep 18 '16 at 11:21
  • @doshin, it does not matter if you have 1000000 nested functions, the reason for the error is the same. – Padraic Cunningham Sep 18 '16 at 11:23
  • @Padraic Cunningham, You're right. Thanks – doshin Sep 18 '16 at 11:29

2 Answers2

2

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.

freakish
  • 54,167
  • 9
  • 132
  • 169
  • Thank you for the answer. Than, why it works if i swap over the arguments? Please see PS1 – doshin Sep 18 '16 at 11:14
  • @doshin Because recursive call in `mult_recursive` depends on second argument, not first. – freakish Sep 18 '16 at 11:32
  • @ freakish 6, right. And it gets at the limit faster. Now I still don;t understand why it doesn't work with 8 if i set a larger recursionlimit. Doesn't work with 10k either. – doshin Sep 18 '16 at 11:42
0

Just to illustrate that you can do it with 8 by setting the recursion depth. Include two statements at the beginning of your code:

import sys
sys.setrecursionlimit(n)

Here n is the recursion depth. If you set it to 5042, the function works fine. For numbers larger than 8, set the recursion depth even higher For example: sys.setrecursionlimit(10000)

gollapudi sravani
  • 9
  • 1
  • Thank you for the answer. I 've changed the limit with both 5042 and 10k and still doesn't work. – doshin Sep 18 '16 at 11:23