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

Comments

• Anonymous
  August 07, 2008
  PingBack from http://blog.a-foton.ru/2008/08/understanding-tail-recursion/

• Anonymous
  August 09, 2008
  So is there a way in VS to quickly know if a function is tail recursive or not?

• Anonymous
  August 09, 2008
  I find it astonishing that in Lisp-like languages (including the ML family), "tail recursion modulo cons" not only has a name, but is rarely implemented. One could generalize this to allowing compilers to exploit associativity, to automatically rewrite your first factorial example as properly tail recursive. I love functional languages. However, in an ideal world one could be required to have a deep understanding of tail recursion (thanks for spreading an explanation) without being forced to keep track of it in practice. In how many languages does one need to worry about folding left versus right, for purely efficiency reasons? This is as barbaric as asking a programmer to allocate registers; shame on the compiler writers. A tail-recursive function is a verbose way to express a grammatical transformation on data, either actual or implied by a computation such as factorial. If we could assume all programmers understood e.g. parsing theory, then languages could emerge with more concise, algebraic descriptions of these transformations. Scripting languages take for granted regular expressions on strings, but no language is as fluid with grammatical transformations of other kinds of data.

• Anonymous
  August 11, 2008
  No, there is no indiciate from the Visual Studio IDE if a function will be compiled as tail-recursive or not. It's something which we've talked about before though.