Doubt about recursion

Python Help
1

Hello,

I have a doubt about how the following recursion works:

’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’
def fact(n):

if n==1:
    return 1
else:
    return n*fact(n-1)

print(fact(4))
’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’

The output is 24, which is the factorial of 4.

I know thath Python has a built-in function which is math.factorial(). But in this case, how is “fact” interpreted as the factorial calculator? I think I’m not understanding how recursion it self works.
Could somoeone please clarify me this doubt?

Thanks very much.

2

Recursion can be confusing, but the key thing to remember is the function stack. If you have a function foo that calls bar, and when bar returns, you go back to the exact point where foo called bar, with all of foo’s local variables “restored”, the same is true if foo calls itself (e.g. recurses).

So, for example, let’s walk through what will happen for fact(4). It will skip over the if since the condition is false, and then it will start executing return 4 * fact(3). The return is the very last thing that will happen; first, Python needs to evaluate the return value, the 4 * fact(3).

So you get a new copy of fact, this time where n is 3. It again skips over the if and starts executing return 3 * fact(2). Again, it can’t actually return before it evaluates the return value, so it recurses further.

This time, you have another fact, where n is 2. All of the same stuff applies, and in trying to evaluate the return value for return 2 * fact(1), it recurses further.

Finally, we get to the base case, because when n == 1, it is able to return 1 without recursing further. So fact(1) will return 1, and execution returns to fact(2), which is now able to evaluate 2 * fact(1) to 2 (using the fact that fact(1) returned 1) and return that value.

It keeps working its way back up the chain in that manner. Execution returns to the invocation of fact(3), which is now able to evaluate 3 * fact(2) to 6 and return that. It returns to fact(4), which is now able to finish evaluating 4 * fact(3) to 24.

Recursion can be confusing, but as long as you keep in mind that when a function calls itself, it also has to return to itself (and not just magically return to the outside when it reaches a return in the base case), it’s not too bad.

1 Like
3

Notice that your function will fail (run forever) for n not an int or less than 1.

One way to help understand a recursive function is to add prints within.

def fac(n):
    print(f'Enter {n}')
    res = n*fac(n-1) if n > 1 else 1
    print(f'Exit {n}, result {res}')
    return res
  
print(fac(4))
1 Like
4

I know thath Python has a built-in function which is math.factorial(). But in this case, how is “fact” interpreted as the factorial calculator? I think I’m not understanding how recursion it self works.
Could somoeone please clarify me this doubt?

See:

5

Yes, I did. Now I’ve understood.

6

It also fails:

>>> fact(1000)
...
RecursionError: maximum recursion depth exceeded in comparison
7

In python, one is better off changing linear recursion (at most 1 recursive call for each call) to while or for loop iteration if recursion depth is a serious possibility.

8

Agreed, but you can sys.setrecursionlimit(1500)

Python wisely doesn’t optimize tail recursion.