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.

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

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

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:

Yes, I did. Now I’ve understood.

It also fails:

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

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.

Agreed, but you can sys.setrecursionlimit(1500)

Python wisely doesn’t optimize tail recursion.