0

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
Improve this question
4
  • 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. Commented Dec 22, 2016 at 9:59
  • This is the basic principle of recursion. The first function to be completely executed is the last called. Commented Dec 22, 2016 at 10:03
  • @ Jean. Which debugger can i use. I only use cmd. Commented Dec 22, 2016 at 10:05
  • 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, as advised by Lakshmi Balan. Commented Dec 22, 2016 at 10:22

2 Answers 2

Reset to default
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/

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

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 ?
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.
Sorry I didn't get this. Is there a way can visualize this process ?
See these 2 links. You will understand it better. youtube.com/watch?v=k0bb7UYy0pY programmerinterview.com/index.php/recursion/…
You can find these links at the bottom of this answer itself. :)
|
0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.