JavaScript呼叫棧、尾遞歸和手動優化的詳細介紹

本篇文章主要介紹了詳解JavaScript呼叫堆疊、尾遞歸和手動優化，具有一定的參考價值，有興趣的小夥伴們可以參考一下

呼叫堆疊（Call Stack）

呼叫堆疊（Call Stack）是一個基本的電腦概念，這裡引入一個概念：堆疊幀。

堆疊幀是指為一個函數呼叫單獨分配的那部分堆疊空間。

當執行的程式從目前函數呼叫另一個函數時，就會為下一個函數建立一個新的堆疊幀，並且進入這個堆疊幀，這個堆疊幀稱為當前幀。而原來的函數也有一個對應的堆疊幀，稱為呼叫幀。每一個堆疊幀裡面都會存入目前函數的局部變數。

當函數被呼叫時，就會被加入到呼叫堆疊頂部，執行結束之後，就會從呼叫堆疊頂端移除函數。並將程式運行權利（幀指標）交給此時棧頂的堆疊幀。這種後進後出的結構也就是函數的呼叫堆疊。

而在JavaScript裡，可以很方便的透過console.trace()這個方法查看目前函數的呼叫幀

尾呼叫

說尾遞歸之前必須先了解什麼是尾呼叫。簡單的說，就是一個函數執行的最後一步是將另一個函數呼叫並回傳。

以下是正確示範：

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

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

1.0程式的最後一步即是執行函數g，同時將其傳回值傳回。 2.0中，尾呼叫並不是非得寫在最後一行中，只要執行時，是最後一步操作就可以了。

以下是錯誤示範：

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

1.0最後一步為賦值操作，2.0最後一步為加法運算操作，3.0隱式的有一句return undefined

#尾呼叫最佳化

在呼叫堆疊的部分我們知道，當一個函數A呼叫另外一個函數B時，就會形成堆疊幀，在呼叫堆疊內同時存在呼叫幀A和目前幀B ，這是因為當函數B執行完成後，還需要將執行權傳回A，那麼函數A內部的變量，呼叫函數B的位置等資訊都必須保存在呼叫幀A中。不然，當函數B執行完繼續執行函數A時，就會亂套。

那麼現在，我們將函數B放到了函數A的最後一步呼叫（即尾呼叫），那還有必要保留函數A的堆疊幀麼？當然不用，因為之後並不會再用到其呼叫位置、內部變數。因此直接用函數B的堆疊幀取代A的堆疊幀即可。當然，如果內層函數使用了外層函數的變量，那麼就仍然需要保留函數A的棧幀，典型例子就是閉包。

在網路上有很多關於講解尾調用的部落格文章，其中流傳廣泛的一篇中有這樣一段。我不是很認同。

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

以下為部落格原文：上面程式碼中，如果函數g不是尾調用，函數f就需要保存內部變數m和n的值、g的調用位置等資訊。但由於呼叫g之後，函數f就結束了，所以執行到最後一步，完全可以刪除 f() 的呼叫記錄，只保留 g(3) 的呼叫記錄。

但我認為第一種中，也是先執行m+n這步操作，再呼叫函數g同時回傳。這應當是一次尾調用。同時m+n的值也透過參數傳入函數g內部，並沒有直接引用，因此也不能說需要保存f內部的變數的值。

總得來說，如果所有函數的呼叫都是尾調用，那麼調用堆疊的長度就會小很多，這樣需要佔用的記憶體也會大大減少。這就是尾調用優化的意思。

尾遞歸

遞歸，是指在函數的定義中使用函數自身的一種方法。函數呼叫自身即稱為遞歸，那麼函數在尾調用自身，即稱為尾遞歸。

最常見的遞歸，斐波拉契數列，普通遞歸的寫法：

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

這種寫法，簡單粗暴，但是有個很嚴重的問題。呼叫棧隨著n的增加而線性增加，當n為一個大數（我測了一下，當n為100的時候，瀏覽器視窗就會卡死。。）時，就會爆棧了（棧溢出，stack overflow）。這是因為這種遞歸操作中，同時保存了大量的棧幀，呼叫棧非常長，消耗了巨大的記憶體。

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

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时实际执行的是这个函数。这种方法可以不用修改原递归函数，当调用递归时只用使用该方法转置一下便可解决递归调用的问题。

总结

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

以上是JavaScript呼叫棧、尾遞歸和手動優化的詳細介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！