1. Tail recursion: The function call itself, called recursion. If the tail calls itself, it is called tail recursion.

Recursion is very memory intensive because you need to store hundreds of call frames at the same time, making it easy to get a “stack overflow” error. But for tail-recursion, since only one call frame exists, a stack overflow error never occurs.

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

factorial(5) // 120
Copy the code

The above code is a factorial function that calculates the factorial of n. At most n calls need to be saved. The complexity is O(n).

If written as tail recursion, only one call record is kept, and the complexity is O(1).

function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
Copy the code

Another well-known example is the calculation of Fibonacci sequence, which can fully illustrate the importance of tail recursive optimization

If it’s a non-tail-recursive Fibonacci recursive method

function Fibonacci (n) { if ( n <= 1 ) {return 1}; return Fibonacci(n - 1) + Fibonacci(n - 2); } Fibonacci(10); // Fibonacci(100) // Fibonacci(500) // Stack overflowCopy the code

If we use tail recursion optimized Fibonacci recursive algorithm

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
Copy the code

As you can see, “tail-call optimization” is so important for recursive operations that some functional programming languages include it in their language specifications. The same is true for ES6, which for the first time explicitly specifies all ECMAScript implementations

Now, tail-call optimization must be deployed. This means that in ES6, as long as tail-recursion is used, there is no stack overflow and relatively less memory. 8.7.4

2. Recursive function rewrite:

Implementations of tail recursion often require rewriting the recursive function to ensure that the last step only calls itself. And the way to do that is to rewrite all the internal variables that you use as arguments to the function. Like the one above

For example, factorial needs to use an intermediate variable, total, so rewrite this intermediate variable as an argument to the function. The downside of this is that it’s not intuitive, it’s hard to see at first glance, why do I have to pass in two parameters, 5 and 1, to compute the factorial of 5? There are two ways to solve this problem. Method one is to provide a function of normal form in addition to the tail-recursive function.

function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
function factorial(n) {
return tailFactorial(n, 1);
}
factorial(5) // 120
Copy the code

The above code looks much more normal by calling the tail recursive function tailFactorial with a normal form of factorial.

There is a concept of functional programming called Currying, which means converting a function that takes multiple arguments to a single argument. You can also use currying here.

function currying(fn, n) {
return function (m) {
return fn.call(this, m, n);
};
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);
factorial(5) // 120
Copy the code

The above code curiorizes the tail recursive function tailFactorial to factorial that takes only 1 argument.

The second, much simpler way is to use ES6’s function defaults.

function factorial(n, total = 1) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5) // 120
Copy the code

In the above code, the parameter total has a default value of 1, so you don’t need to supply this value on the call.

To sum up, recursion is essentially a circular operation. Pure functional programming languages have no looping operation commands, and all looping is implemented recursively, which is why tail recursion is extremely important in these languages

Important. For other languages that support “tail-call optimization” (such as Lua, ES6), just know that loops can be replaced by recursion, and once recursion is used, tail-recursion is best.