递归进阶：自上而下与自下而上的思维差异与实战对比

1. 内容整体设计与思路拆解

在算法这条路上，递归是一道绕不过去的坎。很多人一开始接触递归，记住的只有“函数调用自己”这句废话，真正面对问题的时候，要么不知道递归出口怎么找，要么写出来的代码在 n=30 的时候就开始卡死。我自己带过不少初学算法的朋友，发现他们卡住的最大原因，不是不知道递归语法，而是脑子里始终没有建立起“问题拆解方向”的概念。

《算法很美》第四部分开篇讲递归，直接抛出了两个方向：自上而下（Top-down）和自下而上（Bottom-up）。我当时第一次听到这两个词，第一反应是：这不就是递归和迭代的区别吗？后来才意识到，这个理解太浅了。这两个方向本质上是两种完全不同的思维路径，递归只是其中一种方向的天然载体，而迭代也不是另一种方向的唯一实现方式。

1.1 什么是自上而下

自上而下，也叫自顶向下，指的是从最终目标出发，把一个大问题逐层拆解成规模更小的子问题，直到子问题小到可以直接给出答案，然后再把子问题的结果逐层返回，汇总成大问题的解。

最典型的就是斐波那契数列的朴素递归写法：

int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

这段代码的执行过程，就是从上往下不断调用自己，先把 fib(n) 拆成 fib(n-1) 和 fib(n-2)，再把 fib(n-1) 拆成 fib(n-2) 和 fib(n-3)……一直拆到 fib(0) 和 fib(1) 这两个已知值为止。整个过程像一棵不断往下生长的树，所以叫“自上而下”。

这种方式的优势是思维负担小。只要你找到了递归方程，代码几乎就是照着方程抄一遍。缺点也很明显：如果没有记忆化，大量子问题被重复计算，复杂度会指数级爆炸；递归深度过大时还会栈溢出。

1.2 什么是自下而上

自下而上，也叫自底向上，是反过来从最小子问题开始，先把最底层的答案算出来，再逐步往上推导，最终得到大问题的答案。它不一定非要写成迭代形式，但绝大多数情况下，用迭代实现会让代码更简洁、性能更好。

用斐波那契数列举例，自下而上的写法是从 fib(0)、fib(1) 出发，依次推出 fib(2)、fib(3)……直到 fib(n)：

int fibDp(int n) { if (n <= 1) return n; int prev2 = 0, prev1 = 1; for (int i = 2; i <= n; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; } return prev1; }

这两种方式解决的是同一个问题，使用同一个状态转移方程，区别只是计算的推进方向。

1.3 两种路线的选择标准

我经常被问到：到底用自上而下还是自下而上？我的建议是分情况判断，而不是凭感觉选。

• 如果问题本身就有明确的“大问题拆小问题”结构，而且你一下子就能写出递归方程，那么直接从自上而下入手，先写出朴素递归，再考虑优化。
• 如果递归写出来后存在大量重叠子问题，说明需要记忆化；这时候你可以选择保留递归结构加备忘录，也可以直接改成自下而上的动态规划。
• 如果递归深度可能非常大，比如 n 达到十万甚至百万，那么应该优先考虑自下向上的迭代写法，避免系统栈溢出。
• 如果问题的子问题顺序不直观，难以确定迭代方向，自上而下的记忆化搜索反而是更稳妥的选择。

这里要特别强调一点：自上而下和自下而上不是对立关系，而是同一种状态转移思想的两种表达形式。理解了这一点，后面学动态规划会顺很多。

2. 核心细节解析与实操要点

2.1 递归三要素与状态转移

判断你递归学没学明白，我通常看三件事：递归出口、递归方程、子问题的规模是否递减。这三个要素缺一不可。

递归出口是最容易被忽视的。很多人写递归时先写递归体，后补终止条件，结果要么漏掉，要么条件给错。正确的做法是先问自己：问题最小到什么时候，我能直接给出答案？这个答案就是出口。

递归方程是核心中的核心。它的本质是表达“当前问题的解怎么由更小的子问题构成”。比如斐波那契数列，当前项等于前两项之和；爬楼梯问题，到第 n 阶的方案数等于到第 n-1 阶的方案数加第 n-2 阶的方案数。递归方程找对了，代码只是翻译工作。

子问题规模递减保证递归能结束。如果递归方程里子问题的规模没有变小，那么递归就会无限循环，直到栈爆掉。这是我发现初学者最容易犯的问题之一：递归方程写得热闹，但调用自身时参数没有变化，程序卡死都不知道为什么。

2.2 递归树与复杂度估算

估算递归算法的复杂度，最直观的工具是递归树。拿朴素的斐波那契举例：

• fib(n) 调用 fib(n-1) 和 fib(n-2)；
• fib(n-1) 又调用 fib(n-2) 和 fib(n-3)；
• 每一层调用的数量大约翻一倍，树的高度是 n。

所以朴素的斐波那契递归时间复杂度是 O(2^n)。看到指数级复杂度，第一反应就应该是“存在重叠子问题”。你可以自己画一画递归树，会发现 fib(n-2) 被计算了不止一次，而是多次。

递归树还能帮我们看清空间复杂度。递归的每一层调用都会在系统栈上占用空间，递归树的最大深度就是空间开销，所以朴素递归的空间复杂度是 O(n)。

加了记忆化之后，每个子问题只计算一次，递归树退化成一条链，时间复杂度降为 O(n)。这个从指数级到线性级的飞跃，就是动态规划里“避免重复计算”的直观体现。

2.3 备忘录设计与状态存储

记忆化搜索，说白了就是给递归加缓存。用一个数组或哈希表记录已经算过的子问题结果，下次遇到同样的子问题，直接取缓存，不再重复计算。

我写的斐波那契记忆化递归是这样的：

int fibMemo(int n, vector<int>& memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n]; }

这里需要注意两个细节：

第一，备忘录的初始值要选好。我经常用 -1 表示“还没算过”，因为斐波那契的结果都是非负数，-1 不会和合法结果冲突。如果你的问题里 -1 也可能是合法答案，那就换一个不可能出现的值，比如 INT_MIN，或者干脆用一个布尔数组标记是否计算过。

第二，备忘录的索引范围要提前规划清楚。很多人在递归中直接开一个大小为 n 的数组，结果访问 memo[n] 越界。稳妥的做法是开 n+1 或者更大一点，把索引从 0 开始算好。

记忆化搜索和自下而上的动态规划在时间复杂度和空间复杂度上通常是一样的，只是推进方向不同。我个人的习惯是：正式做题时优先写记忆化搜索，因为它更接近人类思考方式，不容易出错；笔试要求性能时再改成自下而上的迭代版本。

3. 实操过程与核心环节实现

3.1 用斐波那契串起两种思路

斐波那契数列是最经典的教学案例，也是我每次复盘这两个概念时必讲的例子。它足够简单，简单到能让人把所有注意力集中在方向本身。

完整的三层对比是这样的：

我强烈建议你亲手把三个版本都写一遍，然后分别跑 fib(10)、fib(30)、fib(50)，感受一下运行时间的差异。我记得自己第一次跑朴素递归 fib(45) 的时候，笔记本风扇狂转，等了十几秒才出结果；改成迭代版本后，瞬间就算出来了。这种对比带来的冲击，比任何理论解释都管用。

3.2 爬楼梯：自上而下写递归

爬楼梯问题描述很简单：每次可以走 1 阶或 2 阶，问走到第 n 阶有多少种不同的走法。

先不要急着写代码，先想状态。走到第 n 阶，最后一步可能是从第 n-1 阶跨上来，也可能是从第 n-2 阶跨上来。所以走到第 n 阶的方案数 = 走到第 n-1 阶的方案数 + 走到第 n-2 阶的方案数。

于是状态转移方程就是：

f(n) = f(n-1) + f(n-2) f(1) = 1 f(2) = 2

按照自上而下的方式写，递归代码几乎直接翻译方程：

int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; return climbStairs(n - 1) + climbStairs(n - 2); }

这个写法在 n 较大时同样会超时，加上备忘录或者改成自下而上的迭代即可。

我见过很多人在这个题上犯一个边界错误：把 f(0) 定义为 1，然后递归方程写成 f(n) = f(n-1) + f(n-2)，f(1)=1，f(2)=2 也能跑通。但如果你的思路是“到第 0 阶有一种走法（不走）”，这个定义本身没问题，只是比较抽象，容易把自己绕晕。我更推荐初学者把边界定义成具体可感知的 f(1)=1、f(2)=2，等对状态理解透彻了，再考虑更精简的边界。

3.3 归并排序：两种方向的实现对比

归并排序是另一个能很好体现“自上而下”和“自下而上”差别的经典算法。教材上通常讲的是递归版本，也就是自上而下的分治：把数组对半切开，分别排序，再合并。这是理解分治思想的最佳范例。

递归版本的伪代码骨架：

void mergeSort(vector<int>& arr, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }

但归并排序也可以自下而上做：先把数组分成若干个长度为 1 的子数组，两两合并成长度为 2 的有序数组；再把长度为 2 的数组合并成长度为 4 的有序数组……直到整个数组合并完成。这个过程不需要递归调用，只用循环控制合并的步长。

迭代版本的核心思路：

void mergeSortIterative(vector<int>& arr) { int n = arr.size(); for (int len = 1; len < n; len *= 2) { for (int left = 0; left < n - len; left += 2 * len) { int mid = left + len - 1; int right = min(left + 2 * len - 1, n - 1); merge(arr, left, mid, right); } } }

两种实现的时间复杂度都是 O(n log n)，空间复杂度都是 O(n)，但代码的思考方式完全不同。自上而下强调的是“如何把大问题拆成小问题”，自下而上强调的是“如何从小结果拼出大结果”。

我建议你把两个版本都亲手写一遍。写完之后，你会对递归的理解上一个台阶，因为你会发现：同一个算法，换一个方向实现，逻辑完全不一样，但同样的正确。

4. 常见问题与排查技巧实录

4.1 递归超时与重复计算

最常见的问题就是“我的递归代码逻辑明明对的，为什么跑不出结果？”

如果你用 n=50 跑朴素递归斐波那契，卡住了，这不是死循环，而是计算量太大。这时你应该画递归树，看看有没有重叠子问题。一旦发现了重叠子问题，马上就能确定优化方案：要么加备忘录，要么换成自下而上的递推。

我自己的排查顺序是这样的：

1. 先确认递归出口正确，也就是最小的子问题能返回正确结果。
2. 再确认递归方程正确，也就是当前问题的解确实由这些子问题组成。
3. 然后画递归树，观察是否有大量重复节点。
4. 如果有重复节点，加备忘录；如果递归深度过深，直接改迭代。

4.2 栈溢出与迭代改造

递归深度超过系统栈限制时，程序会直接崩溃。我记得有一次在本地测试一个递归遍历二叉树的问题，数据量不大，但是在递归到一万层的时候进程直接崩了。之后养成了一个习惯：只要预估递归深度可能超过几千，就提前考虑迭代写法。

比如斐波那契，递归写法虽然好理解，但在 n 达到十万时，即使有记忆化也不能用递归，因为递归深度就是 n。这种情况只有自下而上的迭代才能稳稳地跑完。顺带提一句，很多动态规划问题都面临同样的问题，这也是为什么算法竞赛选手更偏爱递推而不是递归的原因。

4.3 边界条件和状态方程错误

边界条件写错会导致整体结果错位。最常见的是递归出口返回值给错。比如斐波那契的出口，如果你把 fib(1) 直接返回 1 没问题，但有些变种题会要求 fib(0)=0、fib(1)=1，弄混之后整个结果链全部偏移。

状态转移方程写反方向也经常发生。有的问题是“从前到后”推导，比如爬楼梯；有的问题是“从后到前”推导，比如从终点出发逆推。一旦方向搞反，循环边界和初始值全部跟着乱。我的建议是写自下而上版本时，先把状态转移方程写在纸上，把初始值和循环顺序标清楚，再动键盘。

4.4 常见问题速查表

这张表是我平时调试递归类问题时最常用的排查思路。大部分问题，集中在表里的前两类；而后两类问题，往往是理解了方向之后依然容易踩的深坑。

4.5 一个调试小技巧

最后分享一个我实测下来很省事的调试方法：在小数据规模下，把递归函数的“入参和返回值”全部打印出来。很多人觉得这一步多余，但在排查递归问题时，它比任何调试器都好用。

比如跑 fib(4)，你会看到类似这样的调用序列：fib(4) 调 fib(3) 和 fib(2)，fib(3) 又调 fib(2) 和 fib(1)……把这些调用过程打印出来，哪些子问题被重复计算了，哪里返回值不对，一目了然。等确认逻辑没问题后，再把打印代码删掉，加上备忘录优化即可。

这套方法我用了很多年，从初学者阶段一直到工作岗位，调试复杂递归逻辑时依然有效。打印出来的调用树，就是你的递归树，对照着分析问题，比肉眼盯代码快得多。