Skip to content

递归技巧深入

掌握递归:基础情形、递归情形、尾递归、记忆化和调用栈。

你将学到

  • 基础情形和递归情形设计
  • 调用栈和栈溢出
  • 尾递归及其优化
  • 记忆化避免冗余计算

概念讲解

递归技巧深入

递归是函数调用自身。它是解决具有自相似结构问题的自然方式——树、分形、分治算法。每个递归函数需要两部分:基础情形(何时停止)和递归情形(如何将问题分解为更小的子问题)。

调用栈

每次递归调用在调用栈上添加一个帧,包含局部变量和返回地址。深度递归可能溢出栈——JavaScript 中通常约 10,000 帧。这就是为什么非常深的递归优先使用迭代方案。

尾递归

如果递归调用是最后一个操作,则递归是尾递归的。尾递归函数可被编译器优化为使用常量栈空间(无新帧)。JavaScript 引擎可能在严格模式下优化,但不保证。

记忆化

朴素递归常重复计算相同子问题。斐波那契数列 fib(n) = fib(n-1) + fib(n-2) 无记忆化为 O(2^n) 次调用,有记忆化为 O(n)。记忆化按输入缓存结果,将指数递归变为线性时间。

递归与迭代

每个递归都可使用显式栈转为迭代。当问题天然递归时(树遍历)递归更清晰;当深度无界时迭代更好。

示例代码

              // Naive recursion - exponential time!
function fibNaive(n) { if (n <= 1) return n; return fibNaive(n-1) + fibNaive(n-2); }
// Memoized recursion - linear time
const memo = new Map();
function fibMemo(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const r = fibMemo(n-1) + fibMemo(n-2);
  memo.set(n, r); return r;
}
// Tail-recursive - can be optimized to a loop
function fibTail(n, a = 0, b = 1) { if (n === 0) return a; return fibTail(n-1, b, a+b); }
console.log('Memo:', fibMemo(40));
console.log('Tail:', fibTail(40));
            

朴素版本进行 2^n 次调用。记忆化缓存每个 fib(k),降至 n 次调用。尾递归版本携带累加器 a 和 b。

动手试一试

  • JSON Formatter

    嵌套 JSON 是递归结构——格式化它需要递归遍历。

常见错误

错误写法

忘记基础情形,导致无限递归。

正确做法

每个递归函数必须有不再递归的基础情形。没有它,函数会永远调用自身直到栈溢出。

错误写法

对有重叠子问题的问题使用朴素递归。

正确做法

如果相同子问题被多次求解,添加记忆化。斐波那契和许多动态规划问题从缓存中极大受益。

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误