递归学习日志

按日期追加的递归实战复习日志。方法见《递归方法卡与题单》，2023 年老笔记见 递归。

Day 1（2026-08-29 晚）：数组求和 + 阶乘

首次独立手写递归成功。两题都经历了「写错 → 自己读报错 → 改对」的过程。

知识点清单

• [x] 递归三要素：① 终止条件 → ② 缩小规模 → ③ 组合结果
• [x] 归纳信任：不展开整条调用链，只假设 f(n-1) 是对的，专心写当前层
• [x] 调用栈：先「递」到最底层（base case），再一层层「归」回来，栈是后进先出
• [x] 数组求和：终止条件 = 空数组返回 0；缩小 = 取 arr[0] + 剩余 arr.slice(1)
• [x] 阶乘：终止条件 = n ≤ 1 返回 1；缩小 = n * factorial(n-1)

关键概念（用自己的话）

任何递归题，先问自己三个问题：

1. 终止条件：规模小到什么程度，答案可以直接说出来？ （空数组的和是 0；0 和 1 的阶乘都是 1）
2. 怎么缩小：把规模 n 变成 n-1 或更小？ （数组：去掉第一个元素；阶乘：n → n-1）
3. 怎么组合：用小问题的答案拼出大问题的答案？ （arr[0] + 剩余的和；n × (n-1)!）

核心心法（归纳信任）：不要在大脑里展开整条调用链——人脑装不下。只假设 f(n-1) 已经是对的，专心写「当前这一层」该做什么。

我的理解与举例

递归的本质（我的一句话总结）：递归不是"函数调自己"这个表面动作，本质是把「不知道答案的大问题」不断拆成「同构的、规模更小的问题」，直到拆到能直接回答为止，再把答案一层层传回来。

归纳信任为什么有效：它和数学归纳法是一回事。你不需要（也没能力）在脑子里模拟整条调用链，只要证明两件事：

1. 最底层成立（终止条件对）
2. "n-1 成立"能推出"n 成立"（组合关系对）

这两条成立，整条链就自动成立。写递归的全部工作，就是写对这两件事。

概念举例：

• 终止条件——像俄罗斯套娃：最里面那个最小的娃娃就是终止条件，它不能再拆了，答案直接就是它本身。数组求和里，空数组就是"最小的娃娃"，它的和直接知道是 0。
• 缩小规模——像剥洋葱：每层剥掉最外面一片，剩下的还是一颗洋葱（同构），只是小了一圈。arr.slice(1) 就是"剥掉第一片"。
• 组合结果——像拼乐高：你已经知道"剩下部分拼好的样子"，只需决定"当前这块怎么接上去"。arr[0] + 剩下部分的和 就是"第一块 + 已经拼好的"。
• 归纳信任——像多米诺骨牌：你不用亲手推倒每一块，只要保证"任意一块倒了下一块必倒"（组合对）+ "第一块确实倒了"（终止对），就能放心相信最后一块也会倒。写递归同理：相信 sum(arr.slice(1)) 已经返回正确结果，你只写 arr[0] + 它。

代码示例

数组求和：

function sum(arr) {
  if (arr.length === 0) return 0;    // ① 终止条件：空数组的和是 0
  return arr[0] + sum(arr.slice(1)); // ②③ 缩小 + 组合：第一个元素 + 剩余数组的和
}
console.log(sum([1,2,3,4,5])); // 15

阶乘：

function factorial(n) {
  if (n <= 1) return 1;        // ① 终止条件：0 和 1 的阶乘都是 1
  return n * factorial(n - 1); // ②③ 缩小 + 组合：n × (n-1)!
}
console.log(factorial(5)); // 120

调用栈图（以 factorial(3) 为例）：

factorial(3)          → 等 factorial(2) 的结果
    factorial(2)      → 等 factorial(1) 的结果
        factorial(1)  → 触发终止条件，返回 1   ← 最底层
    factorial(2) 拿到 1 → 返回 2×1 = 2
factorial(3) 拿到 2     → 返回 3×2 = 6          ← 回到最上层

易错点（真实踩坑，务必记住）

1. 返回了函数本身：sum 第一版写成 return sum（返回函数引用），而不是「当前元素 + 剩余的和」。正确是 return arr[0] + sum(arr.slice(1))。
2. 递归调用后的代码执行不到：sum 第一版里 total++ 写在递归调用之后，永远执行不到。要区分「递」（下行）和「归」（上行）两个阶段。
3. 组合里重复调自己：factorial 第一版写成 factorial(n) * factorial(n-1)，左边又调了自己 → 无限递归 → Maximum call stack size exceeded（栈溢出）。正确是 n * factorial(n-1)，用 n 去乘，而不是再调 factorial(n)。

收获：两题都不是一次写对，但都靠自己「读报错 → 定位 → 改对」。这是「我学不会」信念的第一次正面反证。