Python Factorial Recursion function

Question

Can anyone explain to me step by step how this factorial function print out such output ? I don't understand why it print all factorial then follow by intermediate statement, since first n = 5 does not matched n==1 so it will go to else statement and print out intermediate.

def factorial(n):
print("factorial has been called with n = " + str(n))
if n == 1:
    return 1
else:
    res = n * factorial(n-1)
    print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res)
    return res  

print(factorial(5))

factorial has been called with n = 5
factorial has been called with n = 4
factorial has been called with n = 3
factorial has been called with n = 2
factorial has been called with n = 1
intermediate result for  2  * factorial( 1 ):  2
intermediate result for  3  * factorial( 2 ):  6
intermediate result for  4  * factorial( 3 ):  24
intermediate result for  5  * factorial( 4 ):  120
120

just follow the function using a debugger, you'll understand. the first called one doesn't exit as long as there are functions to be called. The call print occurs before the intermediate result. — Jean-François Fabre, Dec 22 '16 at 09:59
This is the basic principle of recursion. The first function to be completely executed is the last called. — iFlo, Dec 22 '16 at 10:03
I recommend manually running this program on paper. Pretend that you're the Python interpreter, and interpret each instruction as it's encountered. Remember to create a fresh local `n` and `res` each time you enter the `factorial` function. It will probably be helpful to think in terms of a [call stack](https://en.wikipedia.org/wiki/Call_stack), as advised by Lakshmi Balan. — PM 2Ring, Dec 22 '16 at 10:22

Lakshmi Balan · Accepted Answer · 2016-12-22T10:45:20.173

3

You are using Recursion function for calculating factorial value. So when you reach this else statement,

else:
    res = n * factorial(n-1)

the control goes to calling the function "factorial(n-1)" again instead of executing next statements. So, when its called again the statement,

print("factorial has been called with n = " + str(n))

will get printed.

Since ,"Stack" data structure is used behind this recursion function. Thus whenever the control goes for function calling statement, the previous state of the program will be pushed into the stack, and popped one by one in a "LIFO" manner. That's why the reason for the output.

See these 2 links. You will understand it better.

https://www.youtube.com/watch?v=k0bb7UYy0pY

http://www.programmerinterview.com/index.php/recursion/explanation-of-recursion/

edited Dec 22 '16 at 10:45

answered Dec 22 '16 at 10:05

Lakshmi Balan

198
12

OK, Now I understand why it printed out factorial statement. But my question now is once n == 1 it should return 1 why it will go to else statement ? How the 'Stack' working in this case ? – user1902849 Dec 22 '16 at 10:29
Good Question. When it goes to n==1 it actually goes to return statement. Thus only TOP of stack function only returns, then it pops the next state from the stack, that itself is a function calling statement. Hope you understood the flow. – Lakshmi Balan Dec 22 '16 at 10:34
Sorry I didn't get this. Is there a way can visualize this process ? – user1902849 Dec 22 '16 at 10:41
See these 2 links. You will understand it better. https://www.youtube.com/watch?v=k0bb7UYy0pY http://www.programmerinterview.com/index.php/recursion/explanation-of-recursion/ – Lakshmi Balan Dec 22 '16 at 10:43
You can find these links at the bottom of this answer itself. :) – Lakshmi Balan Dec 22 '16 at 10:45
Excellent. Now I understood. Thanks – user1902849 Dec 22 '16 at 10:54

score 0 · Answer 2 · answered Dec 22 '16 at 10:07

Indeed, n=5 in first call. So you print "factorial has been called...", then don't enter "if n == 1" and go to "else", which first calls factorial with a local n = 4, and after prints "intermediate result...". Each call of factorial is expected to print those two, except for the last, factorial(1) call, which doesn't execute the else statement, and so doesn't print the "intermediate" thing.

Python Factorial Recursion function

2 Answers2