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 foo
called 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 n
is 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 fact
, where n
is 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 fact(1)
returned 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 24
.
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.