# [Tutor] Problem with python

Steven D'Aprano steve at pearwood.info
Wed Oct 20 12:13:39 CEST 2010

```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

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:
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
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
Starting factorial calculation with n = 1
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
Starting factorial calculation with n = 4
Starting factorial calculation with n = 3
Starting factorial calculation with n = 2
Starting factorial calculation with n = 1
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
```