Recursion - Python, return value question

Question

I realize that this may sound like a silly question, but the last time I programmed it was in assembler so my thinking may be off:

A recursive function as so:

def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n - 1)

Why is it that when the function reaches n == 0 that it does not return 1 but rather the answer which is the factorial. I am thinking something like in assembler it would be when n == 0:

mov eax, 1
ret

Why does the code above work, I suppose python returns the last value on the stack before that condition ?

Answer 1

Think about like this, for fac(5) for example:

return 5 * fac(4)
           return 4 * fac(3)
                      return 3 * fac(2)
                                 return 2 * fac(1)
                                            return 1 * fac(0)
                                                       1

So 1 will be the first returned value but it will be returned to fac(1) and fac(1) will be returned to fac(2) and so on.

Answer 2

It does return 1 when n == 0. That return value is popped off the stack from the calling site, which was the invocation at n * fac(n - 1). That 1 is multiplied by n and returned, etc.

Answer 3

If you call fac(0) it will return 1 (not 0, but I suppose that's just a typo in your question). If you call fac(1), it will go in the else clause, and there it will call fac(0). This will return 1. It will then calculate n*1, which is 1, and return that. If you call fac(2) it will also go in the else clause, where it will call fac(1) which as mentioned above will return 1, so n*fac(n-1) will be 2 and that's the return value of fac(2). And so on. I hope that explained it for you.

Answer 4

Nothing's being implicitely returned - when n=0, the function is entering the if statement, and returning 1 directly from the return 1 statement. However, this isn't the point at which the "answer which is the factorial" is returned to the user. Instead, it may be returning this value to the calling function invoked by fac(1), which in the middle of the n * fac(n - 1) branch. Thus it will take the "1" returned and return n*1, which is 1 to it's caller. If that's fac(2), it'll return n * 1, or 2 to it's caller and so on.

Thus fac(5) gets translated like:

fac(5) = 5 * fac(4) = 5 * (4 * fac(3) = 5 * (4* (3 * fac(2)) = 5 * (4* (3 * (2 * fac(1)) = 5 * (4* (3 * (2 * (1 * fac(0)) = 5*4*3*2*1*1

Only after the 1 value gets returned through each upper layer does it get back to the first caller, and the multiplication at each stage gives you the answer.

Answer 5

James, when the final call to your function (when n==0) returns it's just one of several instances of fac(n) on the call stack. If you say print(fac(4)), the stack is essentially:

fac(0)
fac(1)
fac(2)
fac(3)
fac(4)
print()

The final call to fac(0) appropriately returns 1, however in Python you've requested the return value of the first call to fac(n), fac(4).

Don't think of it as a loop wherein 'ret' will break out, the return simply concludes one of several pending executions.