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

递归这东西我见过太多人卡在同一个地方能看懂代码但自己写不出来能写出一个能跑的版本但一遇到“这题到底该用递归还是迭代”“为什么递归超时了”“什么叫状态转移方程”就彻底懵了。我自己学《算法很美》第四章“深入递归”的时候最大的收获不是多背了几个模板而是彻底弄明白了“自上而下”和“自下而上”这两个方向。搞清楚它们递归、分治、回溯、动态规划基本上就串成一条线了。这篇文章我想把这块内容展开讲透适合正在学数据结构与算法、准备笔试面试的读者也适合工作中偶尔需要写点算法逻辑但一直没系统梳理过的人。文章不会只讲概念我会把每一步都拆开为什么这么想、代码怎么写、踩过什么坑、遇到超时怎么排查尽量让你可以直接照着用。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) → 返回 1factorial(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, memoNone): 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空adc空0123a1012b2112c3221注意看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 一句话对比表我先给一个对比表格把核心差异放一起看比看十段文字都管用。维度自上而下递归/记忆化自下而上递推/DP思考方式从大问题出发逐层拆解从小问题出发逐步构建代码可读性通常更直观贴近数学公式有时需要理解填表顺序才能看懂时间复杂度配合记忆化后可以和递推一样一般是最优的迭代计算额外空间递归栈 备忘录通常偏高可滚动数组压缩到很低典型场景树的遍历、回溯、分治斐波那契、背包、编辑距离、最短路径主要风险栈溢出、重复计算状态定义不清、遍历顺序错误一句话总结自上而下优点是思路自然缺点是空间开销大自下而上优点是效率高缺点是状态怎么定义、转移顺序怎么写门槛稍高。4.2 动态规划四步走从暴力递归到空间压缩我建议所有入门者都按这个顺序走不要一上来就写 for 循环填表先写暴力递归只保证“能算对”完全不考虑性能。检查递归树看有没有大量重复子问题。如果有加备忘录。把递归函数里的状态参数映射成数组下标把递归调用改成循环填表。分析依赖关系如果某个状态只依赖相邻的几个状态用滚动数组或降维压缩空间。我用爬楼梯完整走一遍第一步是暴力递归版本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 刷题路径怎么把“方向”用到具体题目里最后分享一个我自己总结的刷题思维惯性。拿到题目后按顺序问自己这个问题能拆成同样结构的小问题吗能拆 → 递归或分治不能拆 → 大概率是模拟或贪心。拆出来的子问题是互相独立的还是大量重叠的独立 → 直接递归或分治重叠 → 考虑记忆化或动态规划。如果走动态规划答案是“最值、计数、方案数”还是“枚举所有方案”前者 → 自下而上填表后者 → 自上而下回溯。日常工作中我常用这个套路处理的不止是题目还有很多业务逻辑。比如把一棵多叉树展开成扁平列表就是递归加前序遍历把聊天记录按规则合并成摘要就是区间动态规划的思路。算法题练的不只是那几个函数而是解决问题时“能不能拆、拆完怎么合”的判断力。我在实际项目里还发现一个特别好用的小习惯拿到复杂递归逻辑后先在草稿纸上把递归树画出来哪怕只画三层也能帮你看清哪些子问题重复了终止条件有没有问题返回值该怎么组合。画着画着思路往往就通了。这比对着屏幕硬想效率高很多。