CODEWITHSUNDEEP
pythonpython-2.7recursionrecursive-datastructures
Ariel
Ariel

Reputation: 547

How does this recursive function in Python work?

I am learning python from the Book: "ThinkPython".

At page 56 (Chapter 6. Fruitful functions) there is a recursive function that calculates the factorial of any number. It does work, however I don't understand why. This is the code:

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

Let's say I try with 3, I guess this is what should happen:

  1. enters the factorial function and n=3
  2. enters the else statement because n is not 0
  3. and here goes back to the beginning to step 1 with n = 2

so it should do the same until n = 0 and return 1 (it will never get to the last lines).

Upvotes: 0

Views: 569

Answers (3)

Valerie
Valerie

Reputation: 43

Your function is:

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

Let's go through an execution of this function step-by-step, starting with n = 3. 

Entering 
STATE 1 
n = 3 
recurse = factorial(3-1)

STATE 2
n = 2
recurse = factorial(2-1)

STATE 3
n = 1
recurse = factorial(1-1)

STATE 4
You now have an n = 0, so you return 1 to STATE 3.

STATE 3
n = 1
recurse = 1
result = 1
return result to STATE 2

STATE 2
n = 2
recurse = 1
result = 2 * 1 = 2
return result to STATE 1

STATE 1
n = 3
recurse = 2
result = 3 * 2 = 6

And then 6, the factorial of 3, is returned to the calling function :D

Recursion really is a tricky thing to confront, it just takes time to get used to it and to the different ways that it can be used.

Upvotes: 4

Noxeus
Noxeus

Reputation: 577

The factorial of n is defined as n * (n-1) * (n-2) etc until 1

So for n = 5 -> 5*4*3*2*1

In the code the factorial is defined as n * whatever the factorial of n-1 is

Python will find out this last part by asking itself: what is the factorial of n-1? Well it is (n-1) * whatever the factorial of (n-1)-1 is.

Do you see the loop/ recursion?

Since for n==0 the factorial will return 1, python can ask itself over and over again what the recursive part is, until it asks itself, what is the factorial of 0?. This part is hardcoded in the first part.

Once it enters this last part, it knows the other answers too! For n == 5:

  • The factorial is 5 * (factorial of 4)
    • The factorial is 4 * (factorial of 3)
      • ...
        • The factorial of 0 is 1.

The factorial of 5 = 5*4*3*2*1

Upvotes: 1

Brian Postow
Brian Postow

Reputation: 12177

You're correct, as far as you go. However, you don't continue far enough. When the factorial(0) call returns, where does it return to? it returns to the 

recurse = factorial (n - 1)

line where n = 1, and then you continue on from there. So, recurse = 1, result = 1* 1 = 1, and returns 1. Again, that goes to the recurse = line in the n=2 case.so, result = 2*1 = 2, and returns that, to the recurse = line where n = 3, so result = 2 * 3 = 6, which is what gets returned.

Upvotes: 1

Related Questions