How to optimize tail calls

This article comes from the public number: Front-end UpUp, by TianTianUp

preface

Often see about 尾递归 these three words, recursive many times, are inseparable from us, nonsense not much to say, this time we comb through about recursive those things.

Here about recursion, here will not repeat, interested can go to check the information.

If we need to understand how to optimize tail recursion, we need to start from the beginning.

• What is a tail call
• What is tail recursion
• How to optimize tail recursion

Tail call

Literally, it is natural to return a function call at the end of the function, usually referring to the last step in the function's execution.

Take, for example

const fn = () => f1() || f2()
// 这里的话, f2函数有可能是尾调用,f1不可能是尾调用

Why isn't the f1 function, let's look at the equivalent form of this function

const fn = function () {
    const flag = f1()
    if(flag) {
        return flag
    } else {
        return f2()
    }
}

It seems to be written here, and by the end call definition, we understand that only the f2 function is called at the tail.

At this point, why say tail call? We think about the traditional recursion in advance, typically first performing a recursive call, and then based on this recursive return value and settling the results, then what are the traditional recursive disadvantages?

• Inefficient and memory-taking.
• If the recursive chain is too long, it may stack overflow

So can we do optimization, this can involve the tail call mentioned above, its principle is what?

According to Mr. Ni Yifeng's explanation in the function extension of es6 is that the function call forms a "call record" in memory, also known as a "call frame", which holds information such as the call location and internal variables. I f A B is called internally in function A a B call frame is also formed above the call frame of B U ntil B run is over and the result is returned to A B call frame disappears. I f function C is also called inside function B there is also a call frame for C and so on. All call frames form a call stack.

The "call frames" and "call stacks" here should be "execution environments" and "call stacks." Because the last operation of the function is called at the end, it is no longer necessary to retain the call frame of the outer layer, but to directly replace the call frame of the outer layer, so it can play an optimized role.

From the above description, we can understand it

• It works like when the compiler detects that a function call is tail-recursive, it overrides the current active record instead of creating a new call record in the function 调用记录
• In this way, we can also understand that different language compilers or interpreters have done 尾递归优化 so that it does not burst the stack.

If this is the case, the optimization of tail recursion depends on the browser, which mainstream browsers support it

Safari and Firefox, interested in getting to know, can write a Fibonacci number of columns to verify.

Manual optimization

Now that we know that many browsers don't have many browsers that support tail-recursive optimization, you'll be curious that when we use tail-recursive optimization, there's still 栈溢出 error, so how do we fix it?

I see a good solution on the Internet, using the trampoline function

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

So how to use it?

Let's take the most common Fibonacci series

function fibonacci(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

Based on the above formula, we can write it as an iteration, using a variable to cache its value

function fibonacci (n, ac1 = 0, ac2 = 1) {
    return n