Computing Fibonacci Numbers

Tail Call Recursion

The reason Python has a stack of function calls is to deal with the case of a function that calls another function and then does something with the result before returning it:

def fact(n):
    """The factorial function."""
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

Computing fact(4) looks like this:

fact(4)
= 4 * fact(3)
= 4 * (3 * fact(2))
= 4 * (3 * (2 * fact(1)))
= 4 * (3 * (2 * (1 * fact(0))))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

Python has to store a lot of information for each of those parentheses so it knows to go back to the right place after evaluating each call.

Now let's look at a different function that does the same thing:

def fact2(n, curr_value=1):
    if n == 0:
        return curr_value
    else:
        return fact2(n - 1, curr_value * n)

Now evaluating this looks a little different:

fact2(4, 1)
= fact2(3, 4)
= fact2(2, 12)
= fact2(1, 24)
= fact2(0, 24)
= 24

There's no need to remember what the previous function calls were: at each step, we have all of the information we need to get the answer.

This structure is possible whenever the only return statements your function has are just a single expression. It's called tail-call recursion, because all of the recursion happens at the tail of the function.