Skip to content

1. 先定义函数负责什么 ​

递归是让函数通过更小规模的同类问题求解当前问题。开始写代码前,先回答三个问题:

  1. 函数契约:输入是什么,返回值准确表示什么?
  2. 终止条件:哪些最小情况可以直接给答案?
  3. 规模缩小:下一次调用为什么更接近终止条件?

先读复杂度与数据结构基础。本篇只要求能写数组循环、理解函数参数和返回值;树的示例可以在数组示例掌握后再读。

不要一开始就在脑中展开所有调用。先假设子调用能按约定返回正确结果,再检查当前层如何组合它,最后确认每层都朝终止条件前进。

2. 第一个例子:计算数组后缀的和 ​

2.1 从循环思路改写契约 ​

朴素方法是从某个下标开始循环累加,时间为 O(n)、辅助空间为 O(1)。现在改用递归,目的是理解调用与返回,并不是让求和更快。

定义 sumSuffix(nums, start) 返回区间 [start, nums.length) 的元素之和。输入约定:

  • nums 是安全整数数组,本次求和涉及的中间结果也在安全整数范围内。
  • start 是 0 到数组长度之间的整数,省略时为 0。
  • 不修改输入;空后缀的和为 0。

这是教学函数的前提;它不额外校验任意外部输入。负下标、超出长度的下标或小数下标不属于本题契约。

js
function sumSuffix(nums, start = 0) {
    if (start === nums.length) return 0;
    // shortcut: 调用深度随后缀长度增长,处理长数组时改用循环。
    return nums[start] + sumSuffix(nums, start + 1);
}

2.2 为什么成立 ​

当前后缀分成“当前位置的值”和“下一位置开始的后缀”。如果子调用返回后半段的正确和,加上当前位置的值,就得到当前后缀的和。

当 start === nums.length 时,后缀没有元素,直接返回 0。每次将 start 增加 1,剩余长度严格减少,所以满足输入约定时最终会到达空后缀。

这里传递下标,不使用 slice。若每次复制剩余数组,就会额外复制 n - 1、n - 2 等数量的元素,不能再把整个过程当成简单线性扫描。

2.3 手推进入与返回 ​

对 [2, -1, 4] 从下标 0 开始求和:

当前调用等待的计算子调用返回后得到
sumSuffix(nums, 0)2 + sumSuffix(nums, 1)2 + 3 = 5
sumSuffix(nums, 1)-1 + sumSuffix(nums, 2)-1 + 4 = 3
sumSuffix(nums, 2)4 + sumSuffix(nums, 3)4 + 0 = 4
sumSuffix(nums, 3)无需继续调用0

调用时从表格上往下,返回时从下往上。父调用在子调用完成之前,仍需记住当前位置和待执行的加法;这部分状态保存在调用栈中。

若后缀长度为 k,共有 k + 1 次调用,时间与辅助空间均为 O(k + 1);当从头处理非空数组时,通常简写为 O(n)。没有辅助数组,不代表辅助空间为常数。

3. 返回值与副作用不能混淆 ​

return 把结果交给当前调用的调用者;console.log 只负责输出,不会让调用者自动拿到结果。若漏掉返回语句,调用者通常得到 undefined,再用于加法可能得到 NaN。

上面的 sumSuffix 只读输入,用返回值传递答案。每次调用的参数和局部变量独立,但传入的数组仍是同一个对象。若改写 nums,其他调用也会看到变化;递归不会自动复制对象。

写解法时明确选择:是返回一个答案,还是修改共享结果?先掌握返回值写法,再学习需要维护路径、撤销操作的回溯,不要把共享变量与函数返回值混在一起解释。

4. 第二个例子:统计二叉树节点数 ​

4.1 契约与拆分 ​

countNodes(root) 返回以 root 为根的整棵子树的节点数。空树是 null;非空节点具有 left 和 right 字段,孩子为空时也用 null。输入必须是有限、无环且没有共享子节点的二叉树,不是任意图。

一棵非空树可以拆成根节点、左子树和右子树,因此答案是 1 + 左子树节点数 + 右子树节点数。每次递归进入严格更小的子树,最终遇到空树。

js
function countNodes(root) {
    if (root === null) return 0;
    // shortcut: 极深的树可能耗尽调用栈,处理深度不可控的数据时改用显式栈。
    return 1 + countNodes(root.left) + countNodes(root.right);
}

函数不修改树。空树返回 0,叶子节点的两个孩子都返回 0,所以叶子返回 1。节点值可以重复,因为本题按节点计数,不按不同的值计数。

4.2 时间与空间分别看什么 ​

设节点数为 n,树高为 h。每个非空节点处理一次,空孩子调用的总数也是线性量级,因此非空树的时间为 O(n)。同时存在的递归层数由树高决定,辅助空间为 O(h),不能因为左右子树各调用一次就直接说空间翻倍。

平衡树的高度为对数量级,但退化成一条链时高度为 n。树的递归空间不能一律写成 O(log n);时间也不能因为每个节点有两个孩子就写成指数级。

如果输入有环,递归可能无法结束;如果同一个节点被多个父节点引用,本函数会重复计数。图的遍历需要另外定义访问标记与计数语义。

5. 重复子问题与递归边界 ​

并非所有递归都会重复计算同一子问题。数组后缀求和每个下标只访问一次;上面的合法二叉树,每个节点也只访问一次。

朴素斐波那契递推则不同:计算 F(4) 时会调用 F(3) 和 F(2),而计算 F(3) 又需要 F(2),于是同一状态被重复计算。这才是后续学习记忆化与动态规划的切入点。本阶段只需要能画出重复分支,不必马上优化。

数学上能够终止,不等于运行环境能容纳所有调用。JavaScript 的可用调用栈有限且因环境而异;不要给出一个通用的“安全递归层数”。长数组优先使用循环,深度不可控的结构考虑显式栈。也不要仅凭尾调用写法就假定运行环境会优化空间。

6. 验证、练习与下一步 ​

先手推,再运行。本文代码由仓库测试直接读取并执行:

sh
node --test tests/algorithm-recursion-examples.test.mjs
例子必须覆盖的情况关注点
后缀求和空数组、单元素、全负数、重复值、起点在中间或末尾空后缀、下标含义、输入不变
节点计数空树、叶子、左右不对称的树、单侧链、重复节点值返回值组合、没有漏掉单侧分支、输入不变

独立练习,不先看答案:

  1. 对 [3, -2, 5] 从下标 1 开始求和,逐层写出参数、等待的运算和返回值。
  2. 把后缀求和改为循环,比较时间、辅助空间与适用输入规模。
  3. 用自己的话解释:统计节点数时为什么要把左右结果相加,而求树深度时要取较大值?
  4. 间隔至少 3 天后闭卷重写其中一个函数,再用边界用例验证。

能解释上述问题后,再读归并排序的分治过程,以及树专题的深度计算。动态规划和回溯留到学习路线对应阶段,不需要在本篇一次学完。

评论

正在加载评论…