JavaScript函數(shù)調(diào)用棧
理解JavaScript的函數(shù)調(diào)用棧是非常重要的。它可以讓我們知道Javscript在函數(shù)調(diào)用時是怎么運行的。
1. 函數(shù)調(diào)用棧(call stack)
調(diào)用棧是一種棧結(jié)構(gòu),它用來存儲計算機程序執(zhí)行時候其活躍子程序的信息。（比如什么函數(shù)正在執(zhí)行，什么函數(shù)正在被這個函數(shù)調(diào)用等等信息）。
下面我們以一個簡單的例子來看看什么是調(diào)用棧。
function test1(){
var a = 1;
return function test2() {
return a + 1;
}
}
console.log(test1()());
對代碼分析如下：
- 首先運行consol.log(). 這個時候log()方法被調(diào)用.入棧,形成一個棧幀。
- 然后調(diào)用 test1。test1 被調(diào)用，入棧。又形成一個新的棧幀，這個棧幀在之前的棧之上。
- tes1 返回值是一個函數(shù)test2，這個時候被調(diào)用，同時也生成一個棧幀。
- 當test2運行完之后，返回a+1；被推出棧，test1與console.log()依次也被推出棧幀。
還有另外一種情況。在JS中，我們知道還要處理很多異步操作，比如http請求、setTimeout等。他們之中包含有異步函數(shù)。對于這種異步函數(shù)的調(diào)用，JS會把他們放到運行隊列中，在運行之前他們首先會看調(diào)用棧里面是否有等待執(zhí)行的函數(shù)，異步函數(shù)只會在等待調(diào)用棧被清空之后才會入棧執(zhí)行。
對于setTimeout, 它是在等待某個時間之后進入運行隊列。
小結(jié)：
- 當函數(shù)被調(diào)用時，會入棧，形成棧幀。
- 當函數(shù)里在調(diào)用函數(shù)時，內(nèi)部函數(shù)會在外部函數(shù)上再次形成棧幀。
- 函數(shù)運行完之后，會被推出棧。
- 異步函數(shù)運行，首先進入運行隊列，然后在進入棧。
2. Javascript遞歸
- 遞歸函數(shù)時在一個函數(shù)通過名字調(diào)用自身的情況下構(gòu)成的。如：
function factorial(num){
if(num === 1) return num;
return num * factorial(num -1);
}
但是上面的例子在我處理一個非常大的數(shù)的階乘的時候，就會發(fā)生如下的事情：
function factorial(100000) //Uncaught RangeError: Maximum call stack size exceeded
對，沒錯。造成了棧溢出。那我們怎么辦呢？
- 尾遞歸
對于尾調(diào)用可以參考一下阮一峰老師對尾調(diào)用以及尾遞歸的實現(xiàn)的講解。
我們使用之前factorial的例子，來進行尾遞歸。代碼如下：
function factorial(num,total){
if(num === 1) return num;
return factorial(num -1 ,num*total);
}
factorial(10,1) // 3628800
使用尾遞歸可以很輕松的解決了遞歸棧溢出的問題(只保留了內(nèi)層函數(shù)的調(diào)用幀)。
記住:只有不再用到外層函數(shù)的內(nèi)部變量，內(nèi)層函數(shù)的調(diào)用幀才會取代外層函數(shù)的調(diào)用幀，否則就無法進行“尾調(diào)用優(yōu)化”。
但是上面的尾遞歸只能在Javascript的嚴格模式下才能有用。
- 自己實現(xiàn)尾遞歸
怎么實現(xiàn)尾遞歸呢? 我們可以用'循環(huán)函數(shù)'代替遞歸函數(shù).
(1). 使用 trampoline函數(shù)實現(xiàn)尾遞歸。
還是以之前階乘的例子為例。我們知道如下代碼會報出棧錯誤。
function factorial(num){
if(num === 1) return num;
return num * factorial(num -1);
}
我們實現(xiàn)一個 trampoline函數(shù)，這個函數(shù)會不斷的循環(huán)另外一個函數(shù)。
function trampoline(f){
while (f && f instanceof Function){ // 知道f 不是函數(shù) 或空為止，跳出循環(huán)。
f = f();
}
return f;
}
那么 trampoline函數(shù)里的參數(shù)是f是實現(xiàn)階乘邏輯的函數(shù)，也是我們用'循環(huán)'代替遞歸的那個函數(shù)。這個函數(shù)實現(xiàn)如下：
function toFactorial2(n,total){
if(n == 1) return total;
return toFactorial2.bind(null,n-1,n*total);
}
toFactorial2函數(shù)的返回值是toFactorial2使用bind方法綁定的另一個函數(shù)。這樣每次循環(huán)函數(shù)使得前一個toFactorial2 能出棧。這樣就不會造成棧溢出。
接下來我們使用這個函數(shù)。
trampoline(toFactorial2(1000000,1)) //Infinity
(2). 還有另外一種方式。
function tco(f) {
var value;
var active = false;
var accumulated = [];
return function accumulator() {
accumulated.push(arguments);
if (!active) {
active = true;
while (accumulated.length) {
value = f.apply(this, accumulated.shift());
}
active = false;
return value;
}
};
}
var sum = tco(function(x, y) {
if (y > 0) {
return sum(x + 1, y - 1)
}
else {
return x
}
});
sum(1, 100000)
這個函數(shù)才是真正的尾遞歸優(yōu)化，對于尾遞歸優(yōu)化，讀者朋友們可以去看阮一峰老師對尾調(diào)用以及尾遞歸的實現(xiàn)的講解。里面詳解很到位。以上內(nèi)容是我對javscript調(diào)用棧以及遞歸的簡單記錄。
