[TOC] # 原理 我們知道JS中的數據存儲分為棧和堆，程序代碼運行都需要一定的計算存儲空間，就是棧了，棧遵循先進后出的原則，所以程序從棧底開始運行計算，程序內部函數的調用以及返回會不停的執行進棧和出棧的操作，棧內被所占的資源也在不斷的對應變化，但是一旦你的調用即進棧操作過多，返回即出棧不夠，這時候就會導致棧滿了，再進棧的就會溢出來。 # 階乘 計算階乘的例子: ~~~js function fac(n){ return n<1? 1 : n*fac(n-1); } ~~~ 當我們把參數改成改成非常大，會觸發堆棧溢出。 原因是每次執行代碼時，都會分配一定尺寸的棧空間（Windows系統中為1M），每次方法調用時都會在棧里儲存一定信息（如參數、局部變量、返回值等等），這些信息再少也會占用一定空間，成千上萬個此類空間累積起來，自然就超過線程的棧空間了。那么如何解決此類問題？ # 優化 ## 尾遞歸 改成尾遞歸之后是: ~~~js function fac(n, r=1){ return n<1? r : fac(n-1, r*n); } ~~~ (注意尾遞歸中的fac的參數r保存了臨時的計算結果, 函數返回回溯時不需要做任何額外的計算) ## 使用蹦床函數改為循環 ~~~ function trampoline(f){ var func = f; while (typeof func === 'function'){ func = func(); } return func; } ~~~ 然后將我們的尾遞歸函數改成: ~~~js function fac_impl(n, r){ return n<1? r : fac_impl.bind(null, n-1, r*n); } function fac(n){ return trampoline(fac_impl.bind(null, n, 1)); } ~~~ 注意bind的使用, 這里fac\_impl函數并不會直接進行遞歸調用而是返回下一步的調用交給trampoline來循環調用, 這樣調用棧就不會增長了 ## CPS變換 ~~~js function fib(n){ return n<1? 1 : fib(n-1)+fib(n-2); } ~~~ 進行CPS變換: ~~~js function fib_impl(n, cont){ return n<1? cont(1) : fib_impl.bind(null, n-1, function(x){ return fib_impl.bind(null, n-2, function(y){ return cont.bind(null, x+y); }); }); } function fib(n){ return trampoline(fib_impl.bind(null, n, function(r){ return r; })); } ~~~ # 參考資料 [怎樣避免JavaScript中過長遞歸導致的堆棧溢出？](https://www.zhihu.com/question/30078697)