The problem of understanding the classic recursive factorial example in Python 2.7
I understand the concept of recursion where I am confused about flow control. I've seen this presented in two ways: I get it in part, the other doesn't. Example 1:
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
So in this example, if we run fact (3), the following happens:
fact(3) = 3*fact(3-1)` fact(2) = 2*fact(2-1) fact(1) = 1*fact(1-1) fact(0) = 1
or in combination: 3*2*1*1 = 6
Now for the following below where I got it worked, in how flow control works. I have it in my head that when a function is called, everything else is suspended until that function completes, at which time the program will return to main. This is what my brain thinks:
def factorial(n):
if n == 0:
return 1
else:
recurse = factorial(n-1)
result = n * recurse
return result
We call factorial (3):
factorial(3)=factorial(2)=factorial(1)=factorial(0)=1
I think this is because after the call is assigned result
, and in my opinion the code never showed up because the thread control pauses main until result
. I think this function is just starting the check n==0
until 1
it returns and then the program will exit.
Help me understand why I cannot imagine this.
source to share
Here is the outline of the program flow. It can be a little confusing to watch, but it might help. Here, different levels of tabs represent different stacks, and each line is a command to be executed by the program.
factorial(3)
| factorial(2)
| | factorial(1)
| | | factorial(0)
| | | RETURNS 1
| | recurse = 1
| | result = 1 * 1 [since n=1]
| | RETURNS 1 [returning result]
| recurse = 1 [catching returned result of 1]
| result = 2 * 1 [since n=2]
| RETURNS 2 [returning result]
recurse = 2 [catching returned result of 2]
result = 3 * 2 [since n=2]
RETURNS 6 [returning result]
Think about the meaning of the word reentrant - it means that a function can be entered more than once. The function call will block that particular place in the thread, but it will not block the execution of that piece of code on the next call. When the last challenge in the chain returns, it blocks one of them before it and everything becomes unlocked in a chain reaction.
source to share
You are wrong in your understanding that everything else stops before the function returns. This is not the case if, say, function A calls function B. In this situation, A will run until it calls B, after which it will stop, B will start and, assuming that it does not call other functions, returns and A will resume.
In the case of recursion, this means that you have to drill down at each level (A, B, C, D ...) until the if condition allows the function N to complete without calling any other functions. From this point on, the parent functions will resume one by one until you return to "main" as you call it.
I'm on my phone, so typing the example is cumbersome at best. I will definitely write as soon as I get home. Perhaps if you wrote a function that printed "This is function X" (and maybe add some padding), you would render it better.
source to share
There is much less magic in the game than you might think. Each call is factorial
independent of each other, each with its own set of parameters and local variables.
Look at just one level of recursion:
factorial(2)
The control will go into the function and block else
. This is where an internal call takes place factorial
. So the control will enter the function again, run into the block if
and return 1. This ends the internal call.
Meanwhile, the external call was suspended. After the internal call returns, the result is stored in a variable recurse
as control continues. Eventually the outer call returns with 2.
source to share
def factorial(n):
if n == 0:
return 1
else:
recurse = factorial(n-1)
result = n * recurse
return result
So you have an idea what n
is local so that the call factorial(2)
inside factorial(3)
does not get confused with the first calls n
, so there result = n * recurse
will be of result = 3 * 2
instead result = 1 * 1 * 1 * 1
.
Python's scoping rules are that every variable defined inside a function is local. This means that both result
and recurse
exists in several incarnations for each invocation of the factorial, where n > 0
.
Another thing that people have problems with is that each call to the factorial is a completely different incarnation, which is the last one .. In fact it is not, which calls a completely different function:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial2(n-1)
So what happens is that the result of this completely different function causes the factorial to be less than what you need and resumes continuation of the original function by multiplying n
by factorial2 of n-1
and return that result.
Factorial2's code is very similar, but it calls factorial3 and it calls factorial4 again. So there is no recursion, only n different factorial functions, each of which multiplies its own argument with the result for a completely different function that it must wait to compute its own value. This is, of course, silly, because then you will have many identical functions with different names, and the call itself (recursion) will be nothing more than calling a completely different function that does the same thing. In fact, you can think of each call to the same function as if it were a completely different instance that has nothing to do with the previous call, since they do not pass any other data other than what is passed from the caller as arguments.and what is passed back from the callee to the caller, as a result, just as if you were using any other arithmetic function. As long as the answer is being evaluated from the arguments, this will always be true. (every call with the same value always gives the same answer, i.e. functional)
source to share
As Duffimo said, both sections are equivalent, the second is simply split into 3 lines instead of one. If you can understand the first, then what is there not to understand about the second?
recurse = factorial(n-1)
result = n * recurse
return result
coincides with
result = n * factorial(n-1)
return result
coincides with
return (n * factorial(n-1))
The function will start at the number sent (say 3), recursively downward, calling the function again (n-1) -> (3,2,1,0), at 0 it returns 1. Then we are at (3,2,1 ), we use 1 * 1 = 1 and return that. Now we have (3,2) and use 2 * 1 = 2 and return that. We now have (3) where we use 3 * 2 = 6 and return that. With () [nothing left] we are done with recursion.
source to share