Recursion is also a function loop in nature, a call to itself in the function, in some common data structure binary tree, graph and so on using recursion to traverse, search, this section is on the basis of ordinary recursion tail recursion optimization.

In the “Nodejs technology Stack” exchange group, I mentioned that I was asked the question of “tail recursion” in the interview. In addition, I just wrote a binary search tree before, and used a lot of recursive implementation, so I also explained what is tail recursion compared to ordinary recursive call.

What is tail recursion?

After calling a recursive function and getting the return value, the caller simply returns without doing any other calculation! What are the benefits?

“While the program is running, the computer allocates a certain amount of memory for the application; The application allocates its own memory space, part of which is used to record the performance of the various functions being called in the program, which is the function call stack. A regular function call always adds a new stack frame to the top of the call stack. This process is called “pushing” or “pushing” the new frame onto the top of the stack. When the number of calling layers of a function is very large, the call stack will consume a lot of memory, and even burst the memory space (stack overflow) [1], resulting in serious program lag or unexpected crash. The call stack for tail-calls is particularly easy to optimize to reduce memory usage and increase speed. [1] Among them, the optimization effect of tail recursion is the most obvious, especially in the case of very complex recursion algorithm. — Wikipedia”

It’s going to be a little tricky to look at these concepts, but let’s make it clear once and for all with a simple factorial example.

Take N factorial

The factorial formula for any natural number greater than or equal to 1 is: n! = 1 * 2 * 3 * (n -1)n

Ordinary recursive calls

In the following example, instead of returning the factorial of the tail, it does the multiplication, so it’s not a tail recursion.

function factorial(n) {
    if (n === 1) {
        return n;
    }

    return n * factorial(n - 1) // The emphasis is on the tail call return
}

console.log(factorial(5)) / / 120
Copy the code

Its execution process is as follows:

factorial(5)
5 * factorial(5 - 1)
5 * 4 * factorial(4 - 1)
5 * 4 * 3 * factorial(3 - 1)
5 * 4 * 3 * 2 * factorial(2 - 1)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120 / / the result
Copy the code

Tail recursive optimization

We use the ES6 function default to pass in only one value when factorial() is first called, as shown in the following code:

function factorial(n, total = 1) {
    if (n === 1) {
        return total;
    }
    
    return factorial(n - 1, total * n); // The emphasis is on the tail call return
}

console.log(factorial(5)) / / 120
Copy the code

Factorial (n-1, total * n) returns factorial(n-1, total * n). Its execution process is as follows:

factorial(5)
factorial(4.5)
factorial(3.20)
factorial(2.60)
factorial(1.120)
Copy the code

Through the above analysis of the execution process after the general recursion and tail recursion optimization, it is also very clear that the call chain of the recursive call before optimization will continue to strengthen, which will consume more resources than the one after optimization.

Reference

  • Zh.wikipedia.org/wiki/ tail call