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.

// 尾调用错误示范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
}

Tail call optimization

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

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

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

Tail recursion

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.

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

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!