JavaScript调用栈原理、尾递归优化及手动解决爆栈方法

JavaScript调用栈与栈帧机制

调用栈（Call Stack）

调用栈是计算机科学中的基础概念，理解它需要引入“栈帧”这一核心要素。

栈帧是为单次函数调用在栈空间中单独分配的一块内存区域。

当程序从当前函数执行切换到另一个函数时，系统会为该新函数创建一个新的栈帧，并进入该状态，此时新创建的栈帧被称为“当前帧”。而原函数对应的栈帧则被称为“调用帧”。每个栈帧内部都存储着该函数运行所需的局部变量数据。

JavaScript调用栈与栈帧机制

函数被调用时，其栈帧会被压入调用栈的顶部；当函数执行完毕后，该栈帧会从调用栈顶部弹出，并将程序执行权（通过帧指针体现）交还给此时位于栈顶的栈帧。这种后进先出的数据结构构成了函数的调用栈机制。

在JavaScript开发中，可以通过调用 console.trace() 方法来方便地查看当前函数的调用帧信息。

JavaScript调用栈与栈帧机制

尾调用与尾递归概念解析

尾调用

在探讨尾递归之前，必须先明确“尾调用”的定义。简单来说，如果一个函数执行的最后一步操作是调用另一个函数并直接返回其结果，这种调用方式即为尾调用。

以下是正确的尾调用示例：


// 尾调用正确示范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中，由于没有显式返回语句，隐式地返回了 undefined。

尾调用优化原理与V8引擎现状

尾调用优化

如前文所述，当函数A调用函数B时，调用栈中会同时存在A的调用帧和B的当前帧。这是因为当B执行完毕后，需要将执行权返回给A，因此A内部的变量、调用B的位置等上下文信息必须保存在A的栈帧中，否则B执行结束后A无法继续正确运行。

如果我们将函数B的调用置于函数A的最后一步（即尾调用），那么是否还有必要保留函数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内部的变量，因此也不能断言必须保存f内部的变量值。

总体而言，如果所有函数调用均为尾调用，调用栈的长度将显著缩短，从而大幅减少内存占用。这就是尾调用优化的核心含义。

尾递归

递归是指在函数定义中调用函数自身的方法。如果函数在尾调用自身，这种特定的递归形式被称为尾递归。

斐波拉契数列是最常见的递归应用场景，普通递归的写法如下：


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

这种写法虽然简单直接，但存在严重问题。随着参数n的增加，调用栈长度呈线性增长。实测发现，当n达到100时，浏览器窗口甚至会出现卡顿现象。当n为较大数值时，会导致栈溢出（stack overflow）。这是因为普通递归同时保存了大量栈帧，导致调用栈过长，消耗了巨额内存。

接下来，我们将普通递归改写为尾递归形式进行对比。


function fTail(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fTail(n - 1, b, a + b)
}

很明显，其调用栈结构如下：

递归手动优化方案

手动优化

虽然目前暂时无法直接使用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调用栈、尾递归与手动优化方案

JavaScript调用栈与栈帧机制

尾调用与尾递归概念解析

尾调用优化原理与V8引擎现状

递归手动优化方案

实用工具推荐