preface

In this section, we’ll look at what tail-recursion is, the difference between tail-recursion and tail-invocation, and the pros and cons of each.

The tail call

Tail call: The last execution statement of a function is a call to a function. This is called a tail call.

Common mistakes in tail calls:

function f1(x)
    -- Not the last call, the last action is actually return nil
    g(x)  
end

function f2(x)
    The last action is addition instead of calling a function
    return g(x) + 1
end

function f3(x)
    The last action is or, which limits the return value to 1
    return x or g(x)
end

function f4(x)
    The last action is (), which limits the return value to 1
    return (g(x))
end
Copy the code

Tail call elimination:

function f(x) x = x + 1; return g(x) end

After function F calls function G, no more work is needed. This way, when the called function finishes executing, the program no longer needs to return to the original caller. Therefore, after the tail call, the program does not need to keep any information about the called function in the call stack. When g returns, the program’s path is returned directly to f. Some language implementations, such as the Lua language interpreter, take advantage of this feature to make tail calls without using any extra stack space. We call this implementation tail call elimination.

Such as:

function eat(a)
    return 5;
end

function action(a)
    local x = eat()
    return x;
end

function imitate(a)
    local x = action();
    return x;
end

function main(a)
    imitate();
end
Copy the code

The appeal code corresponds to the stack as follows:

But suppose we rewrite the appeal instance code as follows:

function eat(a)
    return 5;
end

function action(a)
    return eat();
end

function imitate(a)
    return action();
end

function main(a)
    imitate();
end
Copy the code

Then the corresponding state of the stack will be as follows:

Advantages:As we can see, since the last call is the last execution statement of the function, there is no need to keep the stack frame of the outer function to store its local variables and the address before the call, so the stack retains only one stack frame from the beginning to the end. This is called tail-call optimization and saves a significant amount of memory space.

Disadvantages: The above is a theoretical ideal, rewriting the code into a tail-call form is only a prerequisite, and whether the stack really retains only one frame from beginning to end depends on the language support. Python, for example, does not support the stack bursting even if it is written in tail recursion form.

Tail recursion

Tail recursion: The function tail calls itself. This form is called tail recursion

For example,factorial:

function factorial(num)
    if num == 1 then
        return 1;
    end
    return num * factorial(num - 1);
end

print(factorial(5));  - 120
print(factorial(500000)); -- stack overflow stack traceback:...
Copy the code

We can see that when we pass num 500000, we exceed the maximum memory range, so we have a stack overflow error. So what if we recursively compute the factorial?

function factorial(num, total)
    if num == 1 then
        return 1;
    end
    return factorial(num - 1, num * total);
end

print(factorial(5.1));  - 120
print(factorial(500000.1)); -- 0 is out of bounds
Copy the code

Advantages: We know that recursion is very space-consuming and prone to stack overflows. If we change it to tail recursion, we can save only 1 stack frame, effectively avoiding stack overflow.

Disadvantages: semantic is not obvious, poor reading

Reference:

Tail calls and tail recursion 1

Tail calls and tail recursion 2