CODEWITHSUNDEEP
pythonrecursionstack
James Dwight
James Dwight

Reputation: 43

Recursion - Python, return value 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 ?

Upvotes: 4

Views: 2215

Answers (5)

Matt Baker
Matt Baker

Reputation: 3754

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.

Upvotes: 0

Khaled Alshaya
Khaled Alshaya

Reputation: 96939

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.

Upvotes: 12

Brian
Brian

Reputation: 119371

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.

Upvotes: 0

sepp2k
sepp2k

Reputation: 370465

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.

Upvotes: 0

Jonathan Feinberg
Jonathan Feinberg

Reputation: 45364

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.

Upvotes: 1

Related Questions