# Tail-call Optimization
**Tail-call optimization is a compiler optimization of functions that utilize tail recursion, that allows these function to be called with a constant stack height. Tail recursion is a specific kind of recursion in which the function directly returns the output of the recursive call, without any additional processing. This allows the compiler to basically merge the two stack frames, without pushing a new one, thus maintaining the stack height.**
Many Functional Programming languages, like F#, support tail-call optimization out of the box, but most object oriented programming languages (C# included) do not. Luckily **tail-call optimization is easily implemented by the user using a technique called the [[Trampoline]].**
## Making sure a function is tail recursive
The [[Factorial]] is one of the basic examples of recursion. The following code for calculating an integer's factorial is not tail recursive as the output of the recursive call is first multiplied by n before being returned.
```fsharp
//Note: this fails for negative inputs and is not tail recursive
let rec f n = if n = 0 then 1 else n * f (n - 1)
```
Such functions can easily be converted to tail recursive ones using the accumulator, or continuations.
### Using the Accumulator
**This method relies on the fact that the factorial function is basically a fold that uses the multiplication [[Monoid]], which allows us to use multiplication's [[Identity]] (1) as the initial value for the accumulator. **
```fsharp
//Note: this fails for negative inputs
let f n =
let rec inner (n', accumulator) =
if n' = 0 then accumulator else inner ((n' - 1), (n' * accumulator))
inner n 1
```
The inner function is tail recursive, meaning that this code will execute with a constant stack height in F#.
### Using Continuations
**Whereas calculating the [[Factorial]] can easily be converted into tail-call recursion because it only requires one recursion call, the same cannot be said when two calls are required such as with the [[Fibonacci Sequence]].**
```fsharp
//Note: this is not tail recursive
let rec fib n =
match n with
| 0 -> 1
| 1 -> 1
| _ -> fib (n - 1) + fib (n - 2)
```
**Continuations are required for these calls. **
```fsharp
//Note: this is slow because no caching is used
//but will have a constant stack height.
//This code fail with negative inputs.
let fib n =
let rec inner n c =
match n with
| 0 -> c 1
| 1 -> c 1
| _ ->
inner
(n-1)
(fun f1 -> inner (n-2) (fun f2 -> c (f1+f2)))
inner n id
```
## Resources
- [Bouncing Around with Recursion](https://johnazariah.github.io/2020/12/07/bouncing-around-with-recursion.html)