递归：让小问题
回答大问题。

STAGE 01 / FOUNDATION第一阶段：理解递归的契约

递归是一种实现方式。先把函数含义说清楚，代码才有可靠的边界与返回值。

1. 递归函数到底在承诺什么？

递归函数会调用自身来求解更小的同类问题。以 fib(k) 为例，它的契约是“返回第 k 个斐波那契数”，并不要求调用者知道它内部怎样计算。写 fib(k - 1) + fib(k - 2) 时，我们使用的是子问题的答案。

2. 为什么这样写是正确的？

可以用数学归纳法理解：边界 0、1 的结果直接正确；假设所有小于 k 的状态都能正确返回，那么把第 k−1 项与第 k−2 项相加，就得到了按定义应有的第 k 项。正确的边界、正确的递推和一定会缩小的规模，三者缺一不可。

3. 递归树画“工作量”，调用栈看“同时存活”

下面是求 F(4) 的完整调用树。相同参数的节点仍是不同的调用，例如 F(2) 会被计算两遍。

Python 先求加号左边，再求右边。父调用等待子调用返回，随后从原来的位置继续执行。观察第一个 F(2) 的返回过程：

进入 F(4) → 进入 F(3) → 进入 F(2) → 进入 F(1)
F(1) 返回 1：F(2) 记住左结果 1
进入 F(0)，返回 0：F(2) 返回 1 + 0 = 1
F(3) 再调用 F(1)，得到 1：F(3) 返回 1 + 1 = 2
F(4) 再调用 F(2)，重复求得 1：F(4) 返回 2 + 1 = 3

STAGE 02 / PATTERNS第二阶段：从核心模板到复杂度

这两题都属于“分解问题、合并返回值”的递归；状态依赖有重叠，适合进一步记忆化。

模板 A：返回型递归

用一条清晰的函数契约贯穿整个过程。以下是语言无关的伪代码，便于迁移；可提交的 Python 完整实现分别放在两题中。

函数 solve(状态):
    如果状态是边界:
        返回边界答案
    左答案 ← solve(更小的状态一)
    右答案 ← solve(更小的状态二)
    返回合并(左答案, 右答案)

模板 B：带记忆化的递归

相同状态若总返回相同答案，就可以只计算一次。键必须包含所有会影响答案的参数。本专题只依赖剩余规模 k，因此用一个整数作键即可；如果问题还依赖位置、背包容量等，就要把这些量一起放入键。

在本次求解开始时建立缓存，并存入边界答案
函数 solve(状态):
    如果状态已在缓存中:
        返回缓存[状态]
    答案 ← 合并(solve(子状态一), solve(子状态二))
    缓存[状态] ← 答案
    返回答案
返回 solve(初始状态)

复杂度：数状态、数转移、数栈深度

对于斐波那契普通递归，函数调用总数满足 C(0)=C(1)=1 和 C(n)=1+C(n−1)+C(n−2)，可得 C(n)=2F(n+1)−1。例如 n=30 时需要 2,692,537 次调用，而记忆化只需要线性次调用。

STAGE 03 / PRACTICE第三阶段：两道典型应用

先从数学定义直接写递归，再从真实计数问题推导同一递推关系。每种解法都给出完整提交代码。

class Solution:
    def fib(self, n: int) -> int:
        def dfs(k: int) -> int:
            if k <= 1:
                return k
            return dfs(k - 1) + dfs(k - 2)

        return dfs(n)

class Solution:
    def fib(self, n: int) -> int:
        memo = {0: 0, 1: 1}

        def dfs(k: int) -> int:
            if k in memo:
                return memo[k]
            memo[k] = dfs(k - 1) + dfs(k - 2)
            return memo[k]

        return dfs(n)

from functools import lru_cache


class Solution:
    def fib(self, n: int) -> int:
        @lru_cache(maxsize=None)
        def dfs(k: int) -> int:
            if k <= 1:
                return k
            return dfs(k - 1) + dfs(k - 2)

        return dfs(n)

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a

class Solution:
    def climbStairs(self, n: int) -> int:
        def dfs(k: int) -> int:
            if k <= 1:
                return 1
            return dfs(k - 1) + dfs(k - 2)

        return dfs(n)

from functools import lru_cache


class Solution:
    def climbStairs(self, n: int) -> int:
        @lru_cache(maxsize=None)
        def dfs(k: int) -> int:
            if k <= 1:
                return 1
            return dfs(k - 1) + dfs(k - 2)

        return dfs(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1

        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

STAGE 04 / ADVANCED第四阶段：用快速倍增把规模减半

继续深化原有两题，不增加题目。掌握线性解法后，再学习“递归一次，同时返回两个相关答案”的设计。

1. 为什么返回相邻两项？

如果递归只返回 F(k)，很难直接构造 F(2k+1)。让 pair(k) 同时返回 (F(k), F(k+1))，就能在一层内用恒等式完成倍增。设 a=F(k)，b=F(k+1)：

对 k≥1，斐波那契加法恒等式给出 F(2k)=F(k)·[F(k−1)+F(k+1)]；再用 F(k−1)=b−a，就得到第一式。另一加法恒等式给出 F(2k+1)=F(k)²+F(k+1)²。k=0 时直接代入 a=0、b=1，两式也都成立。

1. 先递归一次求 pair(m // 2)，得到 a、b。
2. 算出 c=F(2k)、d=F(2k+1)。若 m 为偶数，返回 (c,d)。
3. 若 m 为奇数 m=2k+1，返回 (d,c+d)，即 (F(m),F(m+1))。
4. 递归边界是 pair(0)=(0,1)；每次参数整除 2，深度为 O(log n)。

class Solution:
    def fib(self, n: int) -> int:
        def pair(m: int) -> tuple:
            if m == 0:
                return 0, 1

            a, b = pair(m // 2)
            c = a * (2 * b - a)
            d = a * a + b * b
            if m % 2 == 0:
                return c, d
            return d, c + d

        return pair(n)[0]

3. 为什么爬楼梯 W(n)=F(n+1)？

比较边界：W(0)=1=F(1)，W(1)=1=F(2)。两者都满足“前两项相加”的递推关系，所以由归纳法可得任意 n≥0 都有 W(n)=F(n+1)。这是一项索引偏移，而不是改变了递推式。

class Solution:
    def climbStairs(self, n: int) -> int:
        def pair(m: int) -> tuple:
            if m == 0:
                return 0, 1

            a, b = pair(m // 2)
            c = a * (2 * b - a)
            d = a * a + b * b
            if m % 2 == 0:
                return c, d
            return d, c + d

        return pair(n + 1)[0]

矩阵快速幂也可以在 O(log n) 次矩阵运算内求解同一递推，但需要维护 2×2 矩阵乘法。快速倍增把该递推的代数结构直接浓缩为两项恒等式；本专题优先完整掌握这条进阶路径。

两题对照与核心模板速查

面试时如何解释你的优化？

1. 先建模：说明参数和返回值，列出边界、递推与规模缩小的依据。
2. 找重复：在 F(4) 的递归树标出重复 F(2)，解释为何普通递归是指数时间。
3. 加缓存：相同参数重复出现，记忆化使每个状态只展开一次，时间 O(n)、空间 O(n)。
4. 排顺序：依赖只指向更小状态，改成从小到大的 DP，消除递归栈。
5. 压空间：只读取前两项，用两个变量维护不变量，空间降为 O(1)。
6. 回应追问：若要求更少算术步骤，解释快速倍增；同时说明大整数代价的适用口径。

面试追问与参考回答

四阶段学习计划与长期复习

完成后在第 1、3、7 天各花 10–15 分钟回顾：先遮住代码写出状态与边界，再手推小例子，最后闭卷实现滚动变量。若出错，回到首次失效的不变量或边界；不要只重新抄一遍代码。

掌握清单

清单独立保存；题目进度只由两张题目卡片上的“已掌握”决定。

当你能在不看答案的情况下完成递归建模、正确处理边界、解释复杂度并写出优化代码，再把对应题目标记为“已掌握”。