[Tutor] Problem with python

[Steven D'Aprano]

On Wed, 20 Oct 2010 08:02:43 am Matthew Nunes wrote:

> I cannot understand the how it claimed the code executed, and
> logically it makes no sense to me. Please explain it to me, as I
> have spent hours trying to get my head around it, as the book(in my
> opinion) did not explain it well. Here it is: 

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

To be pedantic, the above code will raise a SyntaxError, because you've 
ignored or lost the indentation. Fortunately in this case it's easy to 
fix:


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


Let's start with an easy example: factorial(0). When Python sees 
factorial(0), it does this:

Call factorial with argument 0:
* if n == 0 <-- this is true, so execute the "if" block: 
    return 1

so the function factorial(0) returns the value 1. All that goes on 
behind the scenes. What *we* see is:

>>> factorial(0)
1

That part is easy. Now, the recursive part. What does Python do when you 
call factorial(1)?

Call factorial with argument 1:
* if n == 0 <-- this is false, so execute the "else" block: 
    recurse = factorial(n-1)

Here Python is calling a function. It happens to be the same function, 
but Python doesn't care about that, and neither should you. So Python 
simply continues:

    Call factorial with argument 1-1 = 0:

Now, we've already seen this above, but Python does the simplest thing 
that could work: it calculates the answer from scratch:

    if n == 0 <-- this is true, so execute the "if" block:
        return 1

Now Python has a value it can assign to recurse, and so it can continue:

    recurse = factorial(n-1) = factorial(0) = 1
    result = n*recurse = 1*1 = 1
    return 1

Wait a second... a couple of lines back, I said n was 1, then I said it 
was 0, and now I'm claiming it is 1 again! What gives?

The difference is that each call to factorial() gets its own local 
variable, n. When you call factorial(1), Python ends up calling the 
function twice: once with n=1, then BEFORE that calculation is 
finished, with n=0, then it falls back to the unfinished calculation.

Here's an example that might explain things better:

def factorial(n):
    print("Starting factorial calculation with n = %d" % n)
    if n == 0:
        print("Done with n = %d -- returning 1" % n)
        return 1
    else:
        print("About to call factorial again...")
        recurse = factorial(n-1)
        result = n*recurse
        print("Done with n = %d -- returning %d" % (n, result))
        return result



And here it is in action:


>>> factorial(0)
Starting factorial calculation with n = 0
Done with n = 0 -- returning 1
1
>>> factorial(1)
Starting factorial calculation with n = 1
About to call factorial again...
Starting factorial calculation with n = 0
Done with n = 0 -- returning 1
Done with n = 1 -- returning 1
1
>>>
>>> factorial(2)
Starting factorial calculation with n = 2
About to call factorial again...
Starting factorial calculation with n = 1
About to call factorial again...
Starting factorial calculation with n = 0
Done with n = 0 -- returning 1
Done with n = 1 -- returning 1
Done with n = 2 -- returning 2
2
>>>
>>>
>>> factorial(5)
Starting factorial calculation with n = 5
About to call factorial again...
Starting factorial calculation with n = 4
About to call factorial again...
Starting factorial calculation with n = 3
About to call factorial again...
Starting factorial calculation with n = 2
About to call factorial again...
Starting factorial calculation with n = 1
About to call factorial again...
Starting factorial calculation with n = 0
Done with n = 0 -- returning 1
Done with n = 1 -- returning 1
Done with n = 2 -- returning 2
Done with n = 3 -- returning 6
Done with n = 4 -- returning 24
Done with n = 5 -- returning 120
120




Notice the pattern of n values: the *first* n value that is used is the 
*last* value to be finished with.


Hope this helps!



-- 
Steven D'Aprano