## Tail Recursion

- Details
- Category: Programming
- Published on Monday, March 23 2015 00:50
- Written by Gary
- Hits: 1027

I wrote a few versions of the factorial function that you can view on GitHub, but I’ll explain them here:

https://gist.github.com/garykpdx/f9b7bb5acf89c273f08b

The first version is a simple recursive factorial function. If the parameter isn’t the base case (n=1) then find the factorial of the next one down. I’ve actually written this so there are two base cases. If n=0 or n=1 then it returns 1. You could write it so that n=1 is not a base case, but the answer comes out the same because it’s just fact(0) * 1, which is 1*1.

### Tail Recursive

This function is not tail recursive, which makes it run more slowly. If a recursive function is tail recursive, then you can always convert it to an iterative version, and vice versa. We can’t do that with this function. In many languages, you really don’t want to write a function as recursive because each call uses stack memory, and this can cause it to blow up at some point, and you don’t know when that will happen. Being able to convert a function into an iterative function is very important.

To make this function tail recursive, we need to add another parameter. This allows us to pass in the additional work instead of performing it in the next step. So we add an accumulator to keep track of the results so far. When it reaches the base case, it doesn’t need to do any more work. It just needs to return the final results. All the work has already been done. You can see this in the second version of the function.

### Iterative

To make this function iterative, all we need to do is change recursion into a loop. Then we change the accumulator parameter into a local variable. Now, instead of putting intermediate results onto the call stack, it’s just a local variable. You can’t make all functions iterative. Some are inherently recursive, such as the Ackermann function.

### Recursion Isn’t Always Bad

Some languages like Java and C# will put each call to a function on the call stack, so using recursion can be problematic. However, there are some languages like Objective Caml and F# that have optimizations so that recursive calls can be automatically converted to iterative implementations by the compiler, as long as they’re tail recursive. So you don’t have to manually convert them to iterative. You just need to make sure they’re tail recursive.