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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
