What is a tail recursion?

Question

In that question I asked about performance. One of the users replied that the compiler does several interesting optimizations, such as inlining, Loop unwinding, tail recursion and caches.

• How Tail Recursion Optimization Works?
• What she does with my code?

Answer 1

I imagine you understand well about recursion, when to use and its advantage over tie.

You must also know how the call stack and that the memory for this has a fixed size determined at the start of the execution, probably placed by the compiler or linkeditor.

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

If you have a large amount of recursive calls accumulates so much that the stack space is depleted, besides being slower to manipulate all this. It can reach the millions and the stack by default has only 1MB. Allocating all this has its cost, save recorders has its cost.

The compiler can identify this situation and turn the recursion into something resembling a loop, so the return that ends up being calculated and used as a parameter happens to be like a local variable in a frame being manipulated in each iteration.

This optimization is usually only possible if the function call is its last instruction.

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

Example of a response in the OS:

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);
}

Turn it 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;
}

Who linearized stays:

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 put in the Github for future reference.

Wikipedia article.

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

Answer 2

Tail recursion is a recursion technique that uses less memory during the stacking process, which makes it faster than common recursion.

In a common recursion, every recursive call made, it is necessary to store the position of the code where the call was made so that it continues from there as soon as it receives 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 store the position where the call was made, since the call is the last operation performed by the function.

A recursion of tail you can use less memory even if you use parameter reference. In this way, each stacked recursive function does not create a memory space for the n and partial parameters, but only updates these two variables without making copies of them.

Full reference