What is a tail recursion?

I imagine you understand recurs well, when to use and your advantage over the loop .

You should also know how call stack works, and that the memory for this has a fixed size determined in start of execution, probably put by the compiler or linker .

If the code of a function calls itself, in each call it will generate a new stack frame with the space for variables, including parameters and return, of this function. This will accumulate on every call.

If you have a large number of recursive calls, you accumulate so much that the stack space is exhausted, as well as being slower to handle all of this. You can reach the millions and the stack by default is only 1MB. Allocating all this has its cost, saving registers has its cost .

The compiler can identify this situation and transform the recursion into something that resembles a loop, so the return that ends up being calculated and used as a parameter becomes a local variable in a unique frame being manipulated in each iteration.

This optimization is only possible if the function call is the last statement itself.

There are some compilers, usually in functional languages that do a deeper analysis and are able to optimize even more complicated cases where the call is not the last, rewriting the entire code. This is important because such languages are often unrelated and may become unfeasible to use some recursions.

Example of a answer in the SO :

unsigned fac(unsigned n) {
    return fac_tailrec(1, n);
}
unsigned fac_tailrec(unsigned acc, unsigned n) {
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Transform into something like this:

unsigned fac_tailrec(unsigned acc, unsigned n) {
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

What linearized is:

unsigned fac(unsigned n) {
    unsigned acc = 1;
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Which in practice is the same as:

unsigned fac(unsigned n) {
    unsigned acc = 1;
    for (; n > 1; --n)
        acc *= n;
    return acc;
}

I placed it on GitHub for future reference.

Wikipedia article .

You can either do it manually or let the compiler do it. You can do optimizations that are difficult for the compiler.

Tail recursion is a recursion technique that uses less memory during the stacking process, making it faster than ordinary recursion.

In a common recursion , for each recursive call, you have to save the position of the code where the call was made to continue from there once you receive the result. For example, if fibonacci (32) makes 7,049,155 recursive calls, it will also take 7,049,155 variables to store the position where the call was made.

In a tail recursion , it is not necessary to save the position where the call was made, since the call is the last operation performed by the function.

A tail recursion may spend less memory even if you use pass-through . Thus, each stacked recursive function does not create a memory space for n and partial parameters, but only updates these two variables without making copies of them.

Complete Reference