--- title: "Tail-Recursion - Explained with the Fibonacci series" description: "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." updated: 2022-05-13 tags: [".NET", "Performance", "C#"] canonical: "https://steven-giesel.com/blogPost/ccdbefd9-2875-49e6-929c-c5081d5b4d27/tailrecursion-explained-with-the-fibonacci-series" --- # 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](https://www.baeldung.com/cs/tail-vs-non-tail-recursion#:~:text=A%20function%20is%20tail%2Drecursive,can%20reuse%20the%20existing%20one.) 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: ```csharp 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)`: ```csharp 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: ```csharp 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. ```no-class ----------------- | 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: ```csharp 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: ```csharp 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): ```csharp 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 `ValueTuple`s as baseline. Here the results: ```csharp | 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: ```csharp 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 `StackOverflowException`s and have better overall performance. ## Resources * Benchmark shown earlier can be found [here](https://github.com/linkdotnet/BlogExamples/tree/main/TailRecursion).