[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)