0

A link to the section I have a question about. Think Python - chapter 6, section 5

This code has me lost. When run, it finds n!, but I don't know how. The part I think I'm misunderstanding is the "recurse = factorial(n-1)" line.

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

  1. Doesn't that call the function and send it back the top? (obviously not, but I'm not sure why not).

  2. Also, after the function finishes breaking down the factors (3! into 3, 2, 1, 1), it then multiplies them. Where is it remembering them?

I'm sure this is simple, but it's got me stumped.

ThiefMaster
  • 310,957
  • 84
  • 592
  • 636
Nate Caleb
  • 11
  • 4
  • 1
    http://stackoverflow.com/questions/717725/understanding-recursion and by the way, your problem is not "think python - section 6.5", but understanding recursion. – tamasgal Jul 18 '13 at 22:57

2 Answers2

6

This is what happens when you run factorial(3):

factorial(3)
  recurse = factorial(2)
    recurse = factorial(1)
      recurse = factorial(0)
        return 1
      return 1 * 1 = 1
    return 2 * 1 = 2
  return 3 * 2 = 6

So in each step of the recursion you have the return value of the inner step and the current value of n.

ThiefMaster
  • 310,957
  • 84
  • 592
  • 636
  • Might be good to point out that the numbers are also temporarily stored on the stack frame as well. – sean Jul 18 '13 at 23:53
  • To make sure I understand, what's getting stored in the stack frame is the fact that each recursion hasn't finished (it's being looped back before it can hit a break, return, or other way to end). It's not until the code finally hits the first part of the if-statement (and returns 1), that the program is finally free to let the other "hanging" function calls go back and finish executing the last two lines for each function call. Is that correct? – Nate Caleb Jul 19 '13 at 14:16
  • Thanks for the help sean, TheifMaster, and septi . . . what I was missing was how the recursion was nesting. That was never explicitly stated. ThiefMaster's indenting was a clue. For some reason, I was thinking that once the function was recursively called, everything left in the function call was "forgotten." Not sure why I thought that though. Anyway, I get it now. Thanks! – Nate Caleb Jul 21 '13 at 01:14
0

I found the stack diagram related to this in Think Python most useful.

stack diagram of factorial(n)

In fact, redrawing it yourself several times will really help nail down the whole recursion thing.

doubledherin
  • 11
  • 1