Understanding Tail Recursion

You may have heard of Tail Recursion before, in fact, you may have even written tail recursive functions before without even knowing it. Even so, why should you care? Safety. Functional programming relies on recursive functions heavily since imperative looping structures are frowned upon. However, recursion chews up a valuable and limited resource – the stack – and can lead to an unrecoverable type of CLR error: the dreaded StackOverflow. Tail Recursion however is a form of recursion that doesn’t use any stack space, and thus is a way to use recursion safely.

Understanding tail recursion is crucial for writing efficient and safe functional code.

Understanding the Stack

A foundational concept in computer programming is the stack, which serves many uses, the most important of which is to know where to continue executing once you exit a function call.

Instruction Pointers and the Stack

Whenever you call a function the instruction pointer (address in the program code that identifies the next operation to execute) is pushed on the stack. Once the function returns a value, the stack is cleared and the instruction pointer is restored. Resuming the program in its previous state.

Consider this simple, recursive function for computing the factorial of a number.

If you set a breakpoint on the final recursion case you will see this callstack. Notice that each recursive call creates a new stack frame. Here you can clearly see the recursive function breaking the parameter x down into smaller and smaller values.

Stack Overflows

Simple enough. But remember that the stack is in a fixed block of memory, and genertaully limited to 1MB. So the factorial function will exhaust the stack for sufficiently large values.  An easier demonstration of this is this infinite loop function:

As soon as you execute this code, you run out of stack space and run into what is known as a stack overflow. Which means that there is no available memory on the stack to continue recusing. The CLR indicates this by throwing a StackOverflowException.

Tail recursion

Tail Call Optimization

Tail Recursion is a specialized type of recursion where there is a guarantee that nothing is left to execute in the function after a recursive call. In other words, the function returns the result of a recursive call.

If there is no additional instructions to execute, then there is no need to store the instruction pointer on the stack, since the only thing left to do once the recursive call exits is restore the stack. So rather than needlessly modifying the stack, tail calls use a GOTO statement for the recursion. And once the recursion eventually succeeds the function will return to the original instruction pointer location.

The previous implementation of factorial was not tail recursive because after the recursive call to factorial (x-1) completed, the function needed to multiply that result by x, the original parameter. This is made clearer if we rewrite the function like this:

 let rec factorial x =
    if x <= 1 then 
        1
    else 
        // Recurse
        let resultOfRecusion = factorial (x - 1)
        // Instruction Pointer needed to be stored so we can resume
        // this function and execute these final two lines
        let result = x * resultOfRecusion
        result

Here is a tail recursive version. By passing the data around as an extra parameter we remove the need to execute code after the recursive function call, so no stack space is required. The result of the recursive call to 'tailRecursiveFactorial’ is the result of the function.

 let factorial x =
    // Keep track of both x and an accumulator value (acc)
    let rec tailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            tailRecursiveFactorial (x - 1) (acc * x)
    tailRecursiveFactorial x 1

The compiled F# code, when viewed under Reflector and converted to C#, looks like this. Which is clearly not going to use up any stack space:

 public static int tailRecursiveFactorial (int x, int acc)
{
    while (true)
    {
        int num = x;
        if (num <= 1)
        {
            return acc;
        }
        acc *= x;
        x--;
    }
}

If we fire up the Visual Studio debugger and set a breakpoint to when the tailRecursiveFactorial function eventually returns the accumulator, you see that only one stack frame has been used.

Again, to sum things up the benefits of using tail recursion are:

• The function executes slightly faster, since no stack pushes and pops are required
• The function can recurse indefinitely since no stack resources are used
• No StackOverflow exceptions