JavaScript函數(shù)調用棧
理解JavaScript的函數(shù)調用棧是非常重要的募舟。它可以讓我們知道Javscript在函數(shù)調用時是怎么運行的薄啥。
1. 函數(shù)調用棧(call stack)
調用棧是一種棧結構,它用來存儲計算機程序執(zhí)行時候其活躍子程序的信息梆掸。（比如什么函數(shù)正在執(zhí)行解寝，什么函數(shù)正在被這個函數(shù)調用等等信息）驼仪。
下面我們以一個簡單的例子來看看什么是調用棧已脓。
function test1(){
var a = 1;
return function test2() {
return a + 1;
}
}
console.log(test1()());
對代碼分析如下：
- 首先運行consol.log(). 這個時候log()方法被調用.入棧,形成一個棧幀珊楼。
- 然后調用 test1。test1 被調用度液，入棧厕宗。又形成一個新的棧幀画舌，這個棧幀在之前的棧之上。
- tes1 返回值是一個函數(shù)test2已慢，這個時候被調用曲聂，同時也生成一個棧幀。
- 當test2運行完之后蛇受，返回a+1句葵；被推出棧，test1與console.log()依次也被推出棧幀兢仰。
還有另外一種情況乍丈。在JS中，我們知道還要處理很多異步操作把将，比如http請求轻专、setTimeout等。他們之中包含有異步函數(shù)察蹲。對于這種異步函數(shù)的調用请垛，JS會把他們放到運行隊列中，在運行之前他們首先會看調用棧里面是否有等待執(zhí)行的函數(shù)洽议，異步函數(shù)只會在等待調用棧被清空之后才會入棧執(zhí)行宗收。
對于setTimeout, 它是在等待某個時間之后進入運行隊列。
小結：
- 當函數(shù)被調用時亚兄，會入棧混稽，形成棧幀。
- 當函數(shù)里在調用函數(shù)時审胚，內部函數(shù)會在外部函數(shù)上再次形成棧幀匈勋。
- 函數(shù)運行完之后，會被推出棧膳叨。
- 異步函數(shù)運行洽洁，首先進入運行隊列，然后在進入棧菲嘴。
2. Javascript遞歸
- 遞歸函數(shù)時在一個函數(shù)通過名字調用自身的情況下構成的饿自。如：
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
對龄坪，沒錯昭雌。造成了棧溢出。那我們怎么辦呢悉默？
- 尾遞歸
對于尾調用可以參考一下阮一峰老師對尾調用以及尾遞歸的實現(xiàn)的講解城豁。
我們使用之前factorial的例子苟穆，來進行尾遞歸抄课。代碼如下：
function factorial(num,total){
if(num === 1) return num;
return factorial(num -1 ,num*total);
}
factorial(10,1) // 3628800
使用尾遞歸可以很輕松的解決了遞歸棧溢出的問題(只保留了內層函數(shù)的調用幀)唱星。
記住:只有不再用到外層函數(shù)的內部變量，內層函數(shù)的調用幀才會取代外層函數(shù)的調用幀跟磨，否則就無法進行“尾調用優(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)化笋熬，讀者朋友們可以去看阮一峰老師對尾調用以及尾遞歸的實現(xiàn)的講解热某。里面詳解很到位。以上內容是我對javscript調用棧以及遞歸的簡單記錄突诬。
