current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 0 down vote favorite

Python is my first programming language, and I'm learning it from "How to Think Like a Computer Scientist". In Chapter 5 the author gives the following example on recursion:

def factorial(n): 
  if n == 0: 
    return 1 
  else: 
    recurse = factorial(n-1) 
    result = n * recurse 
    return result

I understand that if n = 3, then the function will execute the second branch. But what I don't understand is what happens when the function enters the second branch. Can someone explain it to me?

share|improve this question
    
I thing it is clearer if you rewrite the else part by removing the two temporary variable to be just return factorial(n-1) * n. –  richard Jul 26 '14 at 9:00
1  
Just put 3 in and follow the code all the way through the end. Then 4. Then you'll understand. You could do this on paper. –  Jan Doggen Jul 26 '14 at 9:15

2 Answers 2

up vote 2 down vote

What happens is that the function is called again, under the control of the first call, and after that there are two invocations of factorial active simultaneously (but the first one is waiting for the second one to return). Each of them has its own copy of n: the subordinate invocation has n == 2 while the original invocation still has n == 3. The subordinate invocation then calls itself another time, and so on, until there are four versions of the function in memory (but the first three are inactive, waiting for the last one to return).

The variable values and return addresses of all those invocations are kept on the call stack, and they disappear automatically when an invocation returns. (This is why a recursion that is too deeply nested can cause the phenomenon that this site was named after: the stack overflow.)

A good way to get your head around what really happens when a recursive function is called is to simulate the call stack with pen and paper, by writing down what versions of n there are at any given time and what their values are. A call to factorial 3 is just the right size for that exercise.

share|improve this answer
    
So the first time the program reaches "recurse", instead of continuing to "result", it goes back to the start and executes factorial (n-1), which also goes back to the start instead of "result" and so on? –  Ali Mustafa Jul 26 '14 at 13:07
3  
Yes, it goes back to the start, but not quite: control flow moves to the start of another copy of the same method. It's not like running around in a circle, more like entering a car park and reaching the entrance of the next higher level. –  Kilian Foth Jul 26 '14 at 21:55
up vote 1 down vote

I have refracted the code, in the hope that it makes it clearer.

def factorial(n): 
  if n < 0: 
    raise ValueError
  if n == 0: 
    return 1 
  else: 
    return factorial(n-1) * n

It says:

  • I only work for positive numbers
  • 0! = 1
  • n! = (n-1)! × n

This is the definition: we just write the mathematical definition of factorial in python.

Also look at Kilian Foth's answer as it considers stack-overflow problems.

share|improve this answer
    
Note: in python, you will get a stack-overflow for large values of n. This is because python has no tail-call optimisation. (This is a design feature, to allow the implementation of full stack tracing.) –  richard Sep 28 '14 at 8:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.