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.
For example, let’s see what happens when we run factorial(6):
We have to open 6 different frames, just to do the simple factorial calculation. What if n was a million? Or a billion?
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.
how do we make a function tail recursive?
In 61A, the most common way to make a recursive function tail recursive is to create a helper function. Why is this? Well, with regular recursive functions, we are often working towards our base case, and then once we hit the base case, we work backwards, doing calculations at each step to get to our final result. An example of this is with factorial: if we run factorial on, let’s say 6, when we hit the base case of 1, we start working back towards 6, multiplying 1 by 2, and then by 3, and then by 4, and so on, until we multiply by 6 and return the result. But this is clearly not tail recursive because we are doing that multiplication after the recursive calls. What we need to instead do is keep a running product of all of our numbers until we hit our base case, and then return our calculated product. Basically, we should try to do the multiplication as we go, instead of after the recursive calls. To do this, we need to keep track of an extra value: that of our running product. And how to we add in an extra variable to a recursive function? Helper function!
Our final tail recursive factorial function should look like this:
def factorial(n):
def fact_helper(n, result):
if n == 1:
return result
else:
return fact_helper(n - 1, result * n)
return fact_helper(n, 1)
You can see that each time we make a recursive call, we multiply our n value into our result variable, so that by the time we hit the base case of n = 1, result is storing the product of n x (n-1) x (n-2) … x 1, which is what we want as our final result.