Tail-Recursion - Explained with the Fibonacci series

What is Tail-Recursion? We will discover this "special" form of recursion on the example of the Fibonacci series. Also we will check how much faster it is and why.

A regular recursive functions calls itself until some termination criteria is reached.

What is Tail recursion

I will cite from this page:

A function is tail-recursive if it ends by returning the value of the recursive call.

To make it clear we can turn this around and ask ourselves what is a non-tail recursion. And the basic idea would be that we perform our recursive call first and afterwards we do some calculations. With tail-recurive calls we do the opposite. First we calculate everthing and then we go recursive.

Fibonacci

Before we get started with tail-recursive version let us have a look at the "regular" way:

private static int FibonacciRecursive(int n)
{
    if (n <= 1) return n;

    return FibonacciRecursive(n - 2) + FibonacciRecursive(n - 1);
}

What I meant earlier with "recursive first, then calculation" is quite obvious here. We have to call down all the paths of each recursive calls before we can add the values itself. So how does that call look from a compiler a view when he unrolls all that stuff? Let's assume we call FibonacciRecursive(5):

FibonacciRecursive(5)
FibonacciRecursive(3) + FibonacciRecursive(4)
(FibonacciRecursive(1) + FibonacciRecursive(2)) + FibonacciRecursive(4)
(1 + FibonacciRecursive(0) + FibonacciRecursive(1)) + FibonacciRecursive(4)
(1 + 0 + 1) +  FibonacciRecursive(4)
2 + (FibonacciRecursive(2) + FibonacciRecursive(3))
2 + ( (FibonacciRecursive(0) + FibonacciRecursive(1)) + FibonacciRecursive(3))
2 + (0 + 1) + FibonacciRecursive(3)
2 + 1 + FibonacciRecursive(3)
2 + 1 + (FibonacciRecursive(1) + FibonacciRecursive(2))
2 + 1 + (1 + FibonacciRecursive(2))
2 + 1 + (1 + FibonacciRecursive(0) + FibonacciRecursive(1))
2 + 1 + 1 + 0 + 1
5

There is a lot of stuff going on. Especially on important thing: We have to switch constantly the stack frame.

What is a stack frame?

In simple terms a stack frame is a slice of data which gets pushed onto the stack. Each new function has its own stack frame with its own data. This gets "cleaned up" once we exit the function. With that we have an easy way of modelling a lifecycle of static data. I will put a link at the end of this article which talks a bit more about stack and heap if you are interested.

We can visualize that with a simple function:

public int MyRecursiveFunc(int n)
{
    if (n == 1) return 1;

    var a = 2;
    var b = MyRecursiveFunc(n-1);
    return b + a;
}

If we call MyRecursiveFunc(3) we have something like this:

?? This is just a visualization and not how the real stack would look like. For starters the stack grows downwards and not upwards.

 -----------------
|   Stack Frame   |

| ----------------|
| MyRecursiveFunc | <-- Stack Frame of MyRecursiveFunc(1)
| n = 1           |     The top-most entry is the current function
| return 1        |
| ----------------|

| ----------------|
| MyRecursiveFunc | <-- Stack Frame of MyRecursiveFunc(2)
| n = 2           |
| a = 2           |
| ----------------|

| ----------------|
| MyRecursiveFunc | <-- Stack Frame of MyRecursiveFunc(1)
| n = 1           |
| a = 2           |
| ----------------|

Some takeaways from that:

• We can see the more recursive functions we call that way the fuller our stack gets hence after a while we're getting a StackOverflowException because our stack is just at its limit.
• Creating and cleaning those stack frames up is not expensive itself. But doing this extensively will come with its performance cost.

Fibonacci - Tail-recursive

Now let's check the same Fibonacci function with a tail-recurisve approach:

private static int FibonacciTailRecursive(int n, int previous = 0, int current = 1)
{
    if (n == 0)
        return previous;
    if (n == 1)
        return current;
    
    return FibonacciTailRecursive(n - 1, current, previous + current);
}

The main difference here is very clear. We only have one single recursive call and that is the last operation we do in this function. This is important! The compiler:

FibonacciTailRecursive(5, 0, 1);
FibonacciTailRecursive(4, 1, 1);
FibonacciTailRecursive(3, 1, 2);
FibonacciTailRecursive(2, 2, 3);
FibonacciTailRecursive(1, 3, 5); // When n == 1 we abort
5

From a compiler point of view we don't have to create new stack frames at all. It could do that but it doesn't as the compiler knows it's safe to stay in the same stack frame. It knows that because it is safe to assume that there is no changes on the stack frame itself (as our recursion is the last call in the method).

Performance

Let's make a small benchmark like the following (if you want to test yourself, I'll provide the link to this at the end):

public class Fibonacci
{
    public const int FibonacciOf = 25;

    [Benchmark(Baseline = true)]
    public int FibonacciIterativeCall() => FibonacciIterative(FibonacciOf);

    [Benchmark]
    public int FibonacciRecursiveCall() => FibonacciRecursive(FibonacciOf);

    [Benchmark]
    public int FibonacciTailRecursiveCall() => FibonacciTailRecursive(FibonacciOf);
    
    private static int FibonacciIterative(int n)
    {
        if (n <= 1) return n;

        var (previous, current) = (0, 1);
        for (var i = 2; i < n; i++)
        {
            (previous, current) = (current, current + previous);
        }

        return current;
    }

    private static int FibonacciRecursive(int n)
    {
        if (n <= 1) return n;

        return FibonacciRecursive(n - 2) + FibonacciRecursive(n - 1);
    }

    private static int FibonacciTailRecursive(int n, int previous = 0, int current = 1)
    {
        if (n == 0)
            return previous;
        if (n == 1)
            return current;
        
        return FibonacciTailRecursive(n - 1, current, previous + current);
    }
}

We also have an iterative version built with ValueTuples as baseline. Here the results:

|                     Method |          Mean |         Error |        StdDev |     Ratio | RatioSD |
|--------------------------- |--------------:|--------------:|--------------:|----------:|--------:|
|     FibonacciIterativeCall |      27.88 ns |      0.303 ns |      0.253 ns |      1.00 |    0.00 |
|     FibonacciRecursiveCall | 536,531.39 ns | 10,713.264 ns | 24,181.621 ns | 19,897.96 |  911.80 |
| FibonacciTailRecursiveCall |      16.21 ns |      0.357 ns |      0.524 ns |      0.58 |    0.02 |

We see which impact Tail-recursion can have on your code. More than 35000x faster. It is even faster than our iterative example which utilizes ValueTuple. Extensive jumping in the stack-frame is expensive.

Let's use it everywhere then?

As always it very much depends if it is easily achieveable. The Fibonacci version is still very readable and maintainable. Another classic is inverting a binary tree. This is how a normal recursive approach could look like:

public Node Invert(Node node)
{
      if (node == null) return null;

      Node left = Invert(node.Left);
      Node right = Invert(node.Right);
      node.Left = right;
      node.Right = left;
      return root;
}

That is very readable and the intend is very clear. Now you can try to transform this into a Tail Recursive method. That means only 1 recursive call at the very end of the function is allowed. No assignment, no calculation after the recursive call. Yes it will be faster, but also less readable and maintainable. So it depends on your needs.

Conclusion

Tail-recursion is a very nice way to optimize our recursive functions. The compiler will optimize such calls in the way that it doesn't create new stack-frames. So we suffer less from StackOverflowExceptions and have better overall performance.

Resources

• Benchmark shown earlier can be found here.