JavaScript 递归与堆栈

递归是编程中一个重要的概念，而理解 JavaScript 中递归与调用堆栈的关系对于编写高效、可靠的代码至关重要。

递归基础

递归是指函数直接或间接调用自身的过程。一个递归函数通常包含：

1. 基线条件（base case）：停止递归的条件
2. 递归条件（recursive case）：调用自身的条件

function factorial(n) {
  // 基线条件
  if (n === 1) return 1;
  
  // 递归条件
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

调用堆栈（Call Stack）

JavaScript 使用调用堆栈来管理函数调用：

• 每次调用函数时，会创建一个新的栈帧（stack frame）并压入堆栈
• 函数返回时，其栈帧从堆栈弹出
• 递归会导致多个栈帧累积在堆栈中

递归与堆栈的关系

1. 堆栈溢出风险：深度递归可能导致"Maximum call stack size exceeded"错误

   function infiniteRecursion() {
     infiniteRecursion();
   }
   infiniteRecursion(); // 堆栈溢出错误
   

2. 尾调用优化（TCO）：

   • ES6 引入了尾调用优化，但大多数JS引擎未实现
   • 尾递归可以避免堆栈增长，但需要特定写法

   // 非尾递归
   function factorial(n) {
     if (n === 1) return 1;
     return n * factorial(n - 1); // 不是尾调用
   }
   
   // 尾递归形式
   function factorial(n, acc = 1) {
     if (n === 1) return acc;
     return factorial(n - 1, n * acc); // 尾调用
   }
   

递归的替代方案

对于深度递归问题，可以考虑：

1. 迭代：使用循环代替递归

   function factorial(n) {
     let result = 1;
     for (let i = 2; i <= n; i++) {
       result *= i;
     }
     return result;
   }
   

2. 显式堆栈：手动管理堆栈

   function factorial(n) {
     const stack = [];
     while (n > 1) {
       stack.push(n);
       n--;
     }
     let result = 1;
     while (stack.length) {
       result *= stack.pop();
     }
     return result;
   }
   

递归的适用场景

递归特别适合处理：

• 树形结构（DOM遍历、文件系统）
• 分治算法（快速排序、归并排序）
• 数学定义（斐波那契数列、阶乘）

理解递归与堆栈的关系能帮助你更好地调试递归代码，避免堆栈溢出，并选择最合适的算法实现方式。