Detailed introduction to JavaScript call stack, tail recursion and manual optimization

This article mainly introduces the detailed explanationJavaScript call stack, tailrecursion and manual optimization, which has certain reference value. Interested friends can refer to it

Call Stack (Call Stack)

Call Stack is a basic computer concept. Here we introduce a concept: stack frame.

Stack frame refers to the portion of stack space allocated separately for a function call.

When the running program calls another function from the current function, a new stack frame will be created for the next function and this stack frame will be entered. This stack frame is called the current frame. The original function also has a corresponding stack frame, which is called a call frame. Each stack frame will store the local variables of the current function.

When a function is called, it will be added to the top of the call stack. After execution is completed, the function will be removed from the top of the call stack. And give the program running rights (frame pointer) to the stack frame on the top of the stack at this time. This last-in-last-out structure is the call stack of the function.

In JavaScript, you can easily view the calling frame of the current function through the console.trace() method

Tail call

Before talking about tail recursion, you must first understand what tail call is. Simply put, the last step of a function execution is to call and return another function.

The following is a correct demonstration:

// 尾调用正确示范1.0
function f(x){
 return g(x);
}

// 尾调用正确示范2.0
function f(x) {
 if (x > 0) {
  return m(x)
 }
 return n(x);
}

1.0 The last step of the program is to execute function g and return its return value at the same time. In 2.0, the tail call does not have to be written in the last line, as long as it is the last step when executed.

The following is an error demonstration:

// 尾调用错误示范1.0
function f(x){
 let y = g(x);
 return y;
}

// 尾调用错误示范2.0
function f(x){
 return g(x) + 1;
}
// 尾调用错误示范3.0
function f(x) {
 g(x); // 这一步相当于g(x) return undefined
}

The last step of 1.0 is an assignment operation, the last step of 2.0 is an addition operation, and 3.0 implicitly has a return undefined

Tail call optimization

In the call stack part, we know that when a function A calls another function B, a stack frame will be formed. There are both calling frame A and current frame B in the call stack. , this is because after the execution of function B is completed, the execution right needs to be returned to A, so the variables inside function A, the location where function B is called, and other information must be saved in calling frame A. Otherwise, when function B finishes executing and continues to execute function A, everything will go wrong.

So now, we put function B into the last call of function A (that is, the tail call). Is it necessary to retain the stack frame of function A? Of course not, because its calling location and internal variables will not be used again. Therefore, just replace the stack frame of function A with the stack frame of function B. Of course, if the inner function uses variables of the outer function, then the stack frame of function A still needs to be retained. A typical example is a closure.

There are many blog articles on the Internet about explaining tail calls, and one of the widely circulated ones has this paragraph. I don't quite agree.

function f() {
 let m = 1;
 let n = 2;
 return g(m + n);
}
f();
// 等同于
function f() {
 return g(3);
}
f();
// 等同于
g(3);

The following is the original blog text: In the above code, if function g is not a tail call, function f needs to save the values ​​of internal variables m and n, the calling position of g, and other information. But since function f ends after calling g, so in the last step of execution, you can

delete the call record of f() and only keep the call record of g(3).

But I think that in the first method, the m+n step is also performed first, and then the function g is called and returned at the same time. This should be a tail call. At the same time, the value of m+n is also passed into the function g through parameters, and there is no direct

reference, so it cannot be said that the value of the variable inside f needs to be saved.

In general, if all function calls are tail calls, the length of the call stack will be much smaller, and the memory required will also be greatly reduced. This is what tail call optimization means.

Tail recursion

Recursion refers to a method of

using the function itself in the definition of the function. A function calling itself is called recursion, and a function calling itself at the end is called tail recursion.

The most common recursion, the Fibonacci sequence, the way to write ordinary recursion:

function f(n) {
 if (n === 0 || n === 1) return n 
 else return f(n - 1) + f(n - 2)
}

This way of writing is simple and crude, but it has a very serious problem. The call stack increases linearly with the increase of n. When n is a large number (I tested it, when n is 100, the browser window will freeze...), the stack will burst (stack overflow) , stack

overflow). This is because in this recursive operation, a large number of stack frames are saved at the same time, the call stack is very long, and a huge amount of memory is consumed.

接下来，将普通递归升级为尾递归看看。

function fTail(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fTail(n - 1, b, a + b)
}

很明显，其调用栈为

代码如下:

fTail(5) => fTail(4, 1, 1) => fTail(3, 1, 2) => fTail(2, 2, 3) => fTail(1, 3, 5) => fTail(0, 5, 8) => return 5

被尾递归改写之后的调用栈永远都是更新当前的栈帧而已，这样就完全避免了爆栈的危险。

但是，想法是好的，从尾调用优化到尾递归优化的出发点也没错，然并卵：），让我们看看V8引擎官方团队的解释

Proper tail calls have been implemented but not yet shipped given that a change to the feature is currently under discussion at TC39.

意思就是人家已经做好了，但是就是还不能不给你用：）嗨呀，好气喔。

当然，人家肯定是有他的正当理由的：

1. 在引擎层面消除尾递归是一个隐式的行为，程序员写代码时可能意识不到自己写了死循环的尾递归，而出现死循环后又不会报出stack overflow的错误，难以辨别。

2. 堆栈信息会在优化的过程中丢失，开发者调试非常困难。

道理我都懂，但是不信邪的我拿nodeJs（v6.9.5）手动测试了一下：

好的，我服了

手动优化

虽然我们暂时用不上ES6的尾递归高端优化，但递归优化的本质还是为了减少调用栈，避免内存占用过多，爆栈的危险。而俗话说的好，一切能用递归写的函数，都能用循环写——尼克拉斯·夏，如果将递归改成循环的话，不就解决了这种调用栈的问题么。

方案一：直接改函数内部，循环执行

function fLoop(n, a = 0, b = 1) { 
 while (n--) {
  [a, b] = [b, a + b]
 }
 return a
}

这种方案简单粗暴，缺点就是没有递归的那种写法比较容易理解。

方案二：Trampolining（蹦床函数）

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

function f(n, a = 0, b = 1) { 
 if (n > 0) {
  [a, b] = [b, a + b]
  return f.bind(null, n - 1, a, b)
 } else {
  return a
 }
}

trampoline(f(5)) // return 5

这种写法算是容易理解一些了，就是蹦床函数的作用需要仔细看看。缺点还有就是需要修改原函数内部的写法。

方案三：尾递归函数转循环方法

function tailCallOptimize(f) { 
 let value
 let active = false
 const accumulated = []
 return function accumulator() {
  accumulated.push(arguments)
  if (!active) {
   active = true
   while (accumulated.length) {
    value = f.apply(this, accumulated.shift())
   }
   active = false
   return value
  }
 }
}

const f = tailCallOptimize(function(n, a = 0, b = 1) { 
 if (n === 0) return a
 return f(n - 1, b, a + b)
})
f(5) // return 5

经过 tailCallOptimize 包装后返回的是一个新函数 accumulator，执行 f时实际执行的是这个函数。这种方法可以不用修改原递归函数，当调用递归时只用使用该方法转置一下便可解决递归调用的问题。

总结

尾递归优化是个好东西，但既然暂时用不上，那我们就该在平时编码的过程中，对使用到了递归的地方特别敏感，时刻避免出现死循环，爆栈等危险。毕竟，好的工具不如好的习惯。

The above is the detailed content of Detailed introduction to JavaScript call stack, tail recursion and manual optimization. For more information, please follow other related articles on the PHP Chinese website!