Tail call optimization¶
Or more specifically, “How to convert a recursive function into a loop based function with no extra effort”
Replacing a call with a jump instruction is what is effectively Tail Call Optimization (TCO)
The elusive factorial function¶
If you’ve ever come across academic texts on recursive, one of the first few examples you’ll come across is that of either computing a factorial or computing fibonacci. Well, lets example these in more detail, shall we?
Note
As a quick refresher, lets go over what the factorial means: Factorial is generally referred to with a leading ! mark. So 1! would be computing the factorial of 1. Similarly, 5! is computing the factorial of 5. All a factorial really is is as follows: 0! = 1 1! = 1 2! = 2 * 1 3! = 3 * 2 * 1 4! = 4 * 3 * 2 * 1 5! = 5 * 4 * 3 * 2 * 1
Hopefully you are seeing a pattern here at this point: n! = n * (n - 1) * (n - 2) * (n - 2) … 3 * 2 * 1
// Lets state the factorial recursively
uint64_t compute_factorial(uint16_t n)
{
// Base case
if (n == 0)
return 1;
// Recursive case (until we hit the base case)
return n * compute_factorial(n - 1);
}