Recursion can be confusing, but the key thing to remember is the function stack. If you have a function
foo that calls
bar, and when
bar returns, you go back to the exact point where
bar, with all of
foo’s local variables “restored”, the same is true if
foo calls itself (e.g. recurses).
So, for example, let’s walk through what will happen for
fact(4). It will skip over the
if since the condition is false, and then it will start executing
return 4 * fact(3). The
return is the very last thing that will happen; first, Python needs to evaluate the return value, the
4 * fact(3).
So you get a new copy of
fact, this time where
3. It again skips over the
if and starts executing
return 3 * fact(2). Again, it can’t actually return before it evaluates the return value, so it recurses further.
This time, you have another
2. All of the same stuff applies, and in trying to evaluate the return value for
return 2 * fact(1), it recurses further.
Finally, we get to the base case, because when
n == 1, it is able to
return 1 without recursing further. So
fact(1) will return
1, and execution returns to
fact(2), which is now able to evaluate
2 * fact(1) to
2 (using the fact that
1) and return that value.
It keeps working its way back up the chain in that manner. Execution returns to the invocation of
fact(3), which is now able to evaluate
3 * fact(2) to
6 and return that. It returns to
fact(4), which is now able to finish evaluating
4 * fact(3) to
Recursion can be confusing, but as long as you keep in mind that when a function calls itself, it also has to return to itself (and not just magically return to the outside when it reaches a
return in the base case), it’s not too bad.