递归到动态规划：自上而下与自下而上的思维模型全解析

递归这东西，我见过太多人卡在同一个地方：能看懂代码，但自己写不出来；能写出一个能跑的版本，但一遇到“这题到底该用递归还是迭代”“为什么递归超时了”“什么叫状态转移方程”就彻底懵了。我自己学《算法很美》第四章“深入递归”的时候，最大的收获不是多背了几个模板，而是彻底弄明白了“自上而下”和“自下而上”这两个方向。搞清楚它们，递归、分治、回溯、动态规划基本上就串成一条线了。

这篇文章我想把这块内容展开讲透，适合正在学数据结构与算法、准备笔试面试的读者，也适合工作中偶尔需要写点算法逻辑但一直没系统梳理过的人。文章不会只讲概念，我会把每一步都拆开：为什么这么想、代码怎么写、踩过什么坑、遇到超时怎么排查，尽量让你可以直接照着用。

1. 先把递归的本质看清楚——别停留在“函数调自己”

很多教材对递归的定义就一句话，“函数自己调用自己”。这话没错，但太表面了。你真去写代码的时候，光是“自己调用自己”根本不够，你得知道什么时候调、为什么能调、调完之后怎么回来。我在实际带人的时候发现，理解递归真正的钥匙不是“调用”，而是“规模递减”。

1.1 递归三要素：终止条件、递归公式、规模递减

任何一个能正确工作的递归函数，必然同时满足三个条件：

• 终止条件：问题小到某个程度时，直接返回结果，不再调用自己。
• 递归公式：大问题的结果可以由规模更小的同类问题的结果组合出来。
• 规模递减：每次递归调用，问题规模必须朝着终止条件方向变小。

你可以把递归想象成俄罗斯套娃：打开最大的那个，里面是一个小一号的套娃，再打开，又小一号，直到打开最小的那个，里面没有东西了。等最小的那个被“打开”之后，你才能一层一层把外面的套娃重新装回去。递归函数的运行过程，就是这个“打开”和“装回去”的过程。

写成通用模板是这样的：

def solve(n): if n == 基准情况: # ① 终止条件 return 基准结果 return 组合(solve(缩小后的n)) # ② 递归公式 + ③ 规模递减

我在学习初期犯过的最大错误是：只盯着“递推公式”使劲，忽略了终止条件。结果就是函数无限调用自己，直到把系统栈塞满，直接 Stack Overflow。后来我养成一个习惯，写任何递归函数之前，先问自己三个问题：最小的情况是什么？怎么从 n 走到最小的情况？拿到小问题的结果后怎么组合成 n 的结果？三个问题都有答案，代码才动笔。

1.2 系统栈视角：递归为什么会“爆栈”

要理解递归的空间消耗，必须知道函数调用背后发生了什么。每次调用一个函数，系统会把当前函数的局部变量、参数、返回地址压入一个叫“调用栈”的结构里。递归就是不断地调用自己，所以每一层还没返回之前，都会有对应的栈帧存在内存里。深度 n 的递归，峰值就会有 n 层栈帧，这就是递归空间复杂度的来源。

举个简单的例子，求阶乘：

def factorial(n): if n <= 1: return 1 return n * factorial(n - 1)

当 n = 5 时，实际的调用链是这样的：

factorial(5) └── factorial(4) └── factorial(3) └── factorial(2) └── factorial(1) → 返回 1

factorial(5) 要等 factorial(4) 返回，factorial(4) 要等 factorial(3) 返回，以此类推。在 factorial(1) 还没返回之前，前四层的栈帧都还占着内存。如果 n 是十万，十万层栈帧直接溢出。这也是为什么有些语言会对“尾递归”做优化——如果递归调用是函数体里的最后一个操作，编译器可以把当前栈帧直接替换成下一层的栈帧，空间复杂度从 O(n) 降到 O(1)。但注意，Python 默认不做尾递归优化，所以用 Python 写深递归要格外小心。实测下来，Python 里递归深度超过一千就很容易触发 RecursionError，超过一万基本没戏。

2. 自上而下：顺着问题“往下拆”，拆到不能再拆

“自上而下”是我们最自然的一种思考方式。拿到一个大问题，先想“这个大问题能不能拆成几个小问题”，拆出来的小问题如果还是同类问题，就用递归去处理。这个方向贯穿了分治、回溯、树的遍历、甚至编译原理里的递归下降解析。

2.1 经典例子：斐波那契是怎么“拆”的

斐波那契数列的数学定义是F(n) = F(n-1) + F(n-2)，边界是F(0) = 0, F(1) = 1。直接翻译成递归代码几乎是零成本：

def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)

这就是典型的自上而下：要求 F(5)，我先求 F(4) 和 F(3)；要求 F(4)，继续拆成 F(3) 和 F(2)。整个展开过程像一棵树，叫递归树。

问题在哪里？你把 F(5) 的递归树展开就会发现，F(3) 被算了两遍，F(2) 被算了三遍。n 越大，重复计算的次数越恐怖。这个版本的复杂度是 O(2^n)，n = 40 的时候已经要跑几秒，n = 50 基本等不到结果。这个例子特别适合说明“自上而下的直觉写法不一定高效”——不是思路错，而是重复计算太多。

2.2 自上而下的典型战场：树、分治、回溯、语法分析

自上而下不是某一类算法的专属，它几乎无处不在。

• 树的遍历：二叉树的前序遍历就是“先处理根节点，再去遍历左子树和右子树”。每个子树的结构和原树一样，天然适合递归。实际上你根本不需要记忆先序、中序、后序的代码，记住“当前节点做什么，剩余交给递归”就够了。

def preorder(root): if not root: return print(root.val) # 当前节点做什么 preorder(root.left) # 剩余交给递归 preorder(root.right)

• 分治排序：快速排序每一轮选一个基准值，把数组分成左右两部分，然后递归排序左右部分。归并排序则是先递归地把左右半边排好序，再合并两个有序数组。两者拆问题的方向都是自上而下的，区别只在于“合并”这个操作发生在递归前还是递归后。

• 回溯：求全排列、八皇后这类问题，本质上是在一棵“决策树”上做深度优先遍历。每一层决定一个位置选什么，走不通就回到上一层换一个选择。这个“回到上一层”的动作，就是递归函数返回时自带的行为，所以回溯几乎都是自上而下地写。

• 递归下降解析：编译原理里写表达式语法分析器，就是按语法规则自上而下地展开，一个非终结符对应一个递归函数。很多人觉得编译原理难，其实理解了自上而下之后，递归下降解析就是最直观的写法。

2.3 自上而下不高效怎么办：记忆化搜索

针对斐波那契这种重复计算问题，最直接的优化是“把已经算过的结果存起来”，下次用的时候直接查表。这种思路叫记忆化搜索，也叫备忘录递归。

def fib_memo(n, memo=None): if memo is None: memo = {0: 0, 1: 1} if n in memo: return memo[n] memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) return memo[n]

这样每个 n 只会真实计算一次，时间复杂度从 O(2^n) 降到 O(n)。关键是，代码仍然保持“自上而下”的自然思维：还是先拆问题，只是拆出来的子问题结果被缓存了。这个版本是通往动态规划的一座桥，很多动态规划题解里的“记忆化递归”就是它。我自己刷题的习惯是，遇到新题先写一个能跑的版本，哪怕是暴力的；只要发现递归里有大量重复子问题，就立刻上手加备忘录——这是性价比最高的第一步。

3. 自下而上：从小问题“垫”出大问题

“自下而上”是另一个方向：不拆大问题，而是先老老实实把最小的问题算出来，再一步步推出更大的问题。它和递归最大的区别是，通常不需要函数自己调用自己，而是用循环加数组保存中间结果。这就是很多人说“递归改成递推”的本质。

3.1 爬楼梯问题：从递归到填表

爬楼梯问题：有 n 阶台阶，一次可以爬 1 阶或 2 阶，问有多少种不同的方法爬到顶。这个问题的递推关系是dp[i] = dp[i-1] + dp[i-2]，含义是“到第 i 阶的方法数 = 到第 i-1 阶的方法数 + 到第 i-2 阶的方法数”。

自上而下地写，就是记忆化递归；自下而上地写，就是循环填一张表：

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

从左到右填表的过程，就是自下而上的过程：先有 dp[1]、dp[2]，才能推出 dp[3]；有了 dp[3]，才能推出 dp[4]…… 每次都保证“用到的子问题已经算好”。这个循环版本的逻辑非常直白，任何一个学过编程的人都能看懂。如果你再观察一下，发现 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，前面那些数据其实用不到了，于是可以优化成滚动数组：

def climb_stairs_opt(n): if n <= 2: return n a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b

空间从 O(n) 降到 O(1)。这个过程完美演示了自下而上的进化路径：能写递推 → 能压空间。

3.2 二维场景：编辑距离是怎么“填表”的

一维填表还不够，真正体现自下而上威力的是二维动态规划。拿编辑距离来说，问题是把字符串 word1 转换成 word2，允许插入、删除、替换三种操作，求最少操作次数。定义dp[i][j]表示 word1 的前 i 个字符转换成 word2 的前 j 个字符需要的最少操作数。

转移方程分两种情况：

• 如果word1[i-1] == word2[j-1]，那么当前字符不用操作，dp[i][j] = dp[i-1][j-1]。
• 否则，取三种操作的最小值再加一：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

这里的 meaning 是：dp[i-1][j]对应删除 word1 的第 i 个字符，dp[i][j-1]对应在 word1 后插入一个字符，dp[i-1][j-1]对应替换当前字符。自下而上地做，就是先填第 0 行（word1 为空，只能不断插入）和第 0 列（word2 为空，只能不断删除），然后一行一行填上去。

我用一个具体例子说明。把"abc"变成"adc"，初始化后的表格大概是：

注意看dp[3][3]是 1，因为"abc"到"adc"只需要把 b 替换成 d 一次操作。你不可能一开始就看出来这个答案，但只要你从左上角开始，一格一格往右下角填，最后答案自己就出来了。这就是自下而上的核心价值：用确定的顺序把每个状态都算一遍，答案自然浮出水面。二维表也是可以压缩空间的，比如编辑距离只需要上一行和当前行，就可以用两行数组滚动更新，不过理解上先学会完整填表更重要。

3.3 归并排序迭代版：自下而上不只是“递归反着写”

很多人以为自下而上就是把递归函数倒过来写，其实不是。归并排序是最好的反例。

递归版的归并排序是自上而下：把数组对半分，递归排好左右两半，再合并。它的“分”发生在“合”之前，必须先把大问题拆到单个元素，才能开始合并。

迭代版的归并排序则是真正自下而上：一开始把整个数组看成长度为 1 的 n 个小块，每两个相邻小块合并成长度为 2 的有序块，再两两合并成长度为 4 的块，直到整个数组有序。整个过程没有递归调用，只有循环和合并：

def merge_sort_iter(arr): n = len(arr) width = 1 while width < n: left = 0 while left < n: mid = min(left + width - 1, n - 1) right = min(left + 2 * width - 1, n - 1) if mid < right: merge(arr, left, mid, right) left += 2 * width width *= 2 return arr

如果你跳过合并函数只看框架，会发现它比递归版难理解不少。原因就是人类天生习惯自上而下思考，而自下而上要求你先想清楚“最小块是什么、块与块怎么合并、步长怎么扩张”。

类似的还有堆排序里的下沉操作。建堆时我们从最后一个非叶节点开始，自下而上地调整每一棵子树，这样能保证每个节点的左右子树都已经满足堆性质。这里的“自下而上”指的是处理顺序，不是递归方向的逆转。想清楚这一点，很多资料里“建堆可以自下而上”的说法就不会造成困惑了。

4. 两种方向怎么选——一张表和四条经验

很多读者真正关心的问题不是“什么是自上而下、自下而上”，而是拿到题目时“我应该往哪个方向想”。我个人的答案是：大部分时候先用自上而下理解问题，再用自下而上实现方案。

4.1 一句话对比表

我先给一个对比表格，把核心差异放一起看，比看十段文字都管用。

一句话总结：自上而下，优点是思路自然，缺点是空间开销大；自下而上，优点是效率高，缺点是状态怎么定义、转移顺序怎么写，门槛稍高。

4.2 动态规划四步走：从暴力递归到空间压缩

我建议所有入门者都按这个顺序走，不要一上来就写 for 循环填表：

1. 先写暴力递归，只保证“能算对”，完全不考虑性能。
2. 检查递归树，看有没有大量重复子问题。如果有，加备忘录。
3. 把递归函数里的状态参数映射成数组下标，把递归调用改成循环填表。
4. 分析依赖关系，如果某个状态只依赖相邻的几个状态，用滚动数组或降维压缩空间。

我用爬楼梯完整走一遍：第一步是暴力递归版本，f(n) = f(n-1) + f(n-2)；第二步发现 f(3) 被重复计算很多次，加 memo；第三步改成循环填表；第四步发现只需要保存前两个值，用两个变量滚动。这就是从“自上而下想明白”到“自下而上做出来”的标准路径。练熟这条路径之后，你会慢慢发现动态规划也只不过是把递归里“重复的子问题”集中起来处理。

还有一个小技巧：定义 dp 状态时，先从“这个状态代表什么、它的值怎么从更小的状态转移来”开始问。状态定义对了，转移方程基本就顺出来了；状态定义错了，后面再怎么调都是错的。

4.3 什么场景真的只能自上而下

虽然自下而上是效率优选，但有些问题强行自下而上会很别扭，甚至写不出来。

• 回溯类问题：比如八皇后、全排列、数独求解。这类问题需要枚举所有可能路径，并在搜索过程中动态判断是否剪枝。递归调用栈天然就是“当前路径”的轨迹，改成迭代反而要手动维护栈，复杂且容易出错。
• 树形后序遍历：比如计算二叉树的最大路径和。需要先递归处理左右子树，再回到当前节点合并答案，这种后序遍历的顺序本身依赖递归的自然回溯，强行自下而上不如直接递归清晰。
• 依赖关系不明显的搜索问题：比如括号生成，你很难直接定义 dp[i] 表示什么，但用自上而下的 DFS 加剪枝会非常自然。

我的判断标准是：如果问题是“枚举所有方案”或“按照某种树形结构展开”，优先自上而下；如果问题是“求最值、计数、方案数”且可以拆成重叠子问题，优先自下而上。这也是为什么动态规划面试题通常用递推写、回溯题纯粹写递归的原因。

5. 常见问题与避坑实录

这部分整理了我自己学习和带人过程中高频出现的问题，基本能覆盖绝大多数迷茫。

5.1 递归和迭代到底怎么区分

这个问题几乎每次讲算法都会被问到。我的回答特别简单：递归是用“调用子问题”来解决问题，迭代是用“更新状态变量”来解决问题。看阶乘就很直观：

# 递归：需要调用自身 def fact_rec(n): return n * fact_rec(n - 1) if n > 1 else 1 # 迭代：循环里更新结果变量 def fact_iter(n): res = 1 for i in range(2, n + 1): res *= i return res

两者可以互相转化。比如二分查找，递归版很好理解：

def binary_search_rec(arr, target, left, right): if left > right: return -1 mid = (left + right) // 2 if arr[mid] == target: return mid if arr[mid] > target: return binary_search_rec(arr, target, left, mid - 1) return binary_search_rec(arr, target, mid + 1, right)

但实际生产环境里，我更喜欢写迭代版，因为不会爆栈：

def binary_search_iter(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid if arr[mid] > target: right = mid - 1 else: left = mid + 1 return -1

一个实用判断技巧：当你在迭代代码里手动维护了一个栈，并且循环体的行为依赖栈顶元素，你其实就是在手写递归。很多“把递归改成迭代”的面试题，本质就是让你把系统栈换成一个显式的栈。

5.2 三个最容易犯的递归错误

第一个是漏掉终止条件。我见过有人写树的高度时判断条件写反，结果空树直接递归到崩溃。排查的办法是空值、最小值、边界值先跑一遍，比如 n = 0、n = 1、空链表、空树。

第二个是子问题规模没有变小。比如有人写f(n) = f(n + 1)，这永远不会触发终止条件，就是死循环。排查方法是把递归函数里传入的参数打出来，肉眼确认参数是否在向终止条件收敛。

第三个是返回值组合方式错了。比如本来应该是min，写成了max；本来应该是+，写成了*。这个问题最隐蔽，因为程序能跑，结果却不对。排查办法是拿小规模的用例，比如 n = 3、n = 4，手工在纸上算一遍，再和程序输出对比。

5.3 刷题路径：怎么把“方向”用到具体题目里

最后分享一个我自己总结的刷题思维惯性。拿到题目后按顺序问自己：

1. 这个问题能拆成同样结构的小问题吗？能拆 → 递归或分治；不能拆 → 大概率是模拟或贪心。
2. 拆出来的子问题是互相独立的，还是大量重叠的？独立 → 直接递归或分治；重叠 → 考虑记忆化或动态规划。
3. 如果走动态规划，答案是“最值、计数、方案数”，还是“枚举所有方案”？前者 → 自下而上填表；后者 → 自上而下回溯。

日常工作中我常用这个套路处理的不止是题目，还有很多业务逻辑。比如把一棵多叉树展开成扁平列表，就是递归加前序遍历；把聊天记录按规则合并成摘要，就是区间动态规划的思路。算法题练的不只是那几个函数，而是解决问题时“能不能拆、拆完怎么合”的判断力。

我在实际项目里还发现一个特别好用的小习惯：拿到复杂递归逻辑后，先在草稿纸上把递归树画出来，哪怕只画三层，也能帮你看清哪些子问题重复了，终止条件有没有问题，返回值该怎么组合。画着画着，思路往往就通了。这比对着屏幕硬想效率高很多。