Tail Recursion Quick Review

Oftentimes, when we write recursive functions, they can use a lot of space by opening a lot of frames during the recursive process. Tail recursive functions solve this problem by using a constant amount of space. The key to defining a tail recursive function is to make sure that no calculations are done after the recursive call, so that none of the values in the current frame need to be saved.

A non-tail-recursive call:

return x + f(x - 1)

We can see that we still need the value of x, so the current frame must remain open so that after the recursion is complete, we can add in that x value.

A tail recursive call:

return f(x - 1)

No calculations need to be done after the recursion, so the current frame will close, because we don’t need any of the information inside of it once the call is made.