递归是算法面试里的常客也是很多初学者从“会写代码”跨到“懂设计”的第一道门。上次我在社群里看到有人问“动态规划怎么入门”评论区有人甩了一句“先搞清楚自上而下和自下而上”然后就没有然后了。这句话信息量其实很大但单独拿出来说确实容易让人一头雾水。我平时刷题、做项目最常用的两种递归思路也就是这两条自上而下Top-down和自下而上Bottom-up。搞懂它们不仅递归这一块通了后面的动态规划、深度优先搜索、甚至强化学习里的一些时序建模你都会觉得顺畅很多。这篇文章不准备只讲定义我想结合《算法很美》系列里关于递归的那条主线用人话把这两种思路的来龙去脉、适用场景、性能差异、代码套路全盘说透。文章里没有花里胡哨的框架只有我实际调试和刷题过程中验证过的思路和代码。如果你正准备啃递归或者已经在LeetCode上被背包问题虐过这篇文章值得你花15分钟静下心看完。1. 自上而下自下而上递归的两种“灵魂”递归本质上很简单——函数调用自身把一个大的问题拆成有相似结构的子问题。但同样是拆拆的方向和拼回去的顺序直接决定了代码长什么样、性能高不高。这就是标题里“自上而下”和“自下而上”这两个词的真正分量。1.1 自上而下我拆给你看但拆出来先记账自上而下在算法圈里更常见的叫法是“记忆化递归”或者“备忘录递归”。它的思考方式特别符合人类直觉我想解决solve(n)那我可以先解决solve(n-1)再根据solve(n-1)的结果来推现在的答案。用大白话说这就是“先拆解后递归顺便把算过的结果记在小本本上”。举个例子斐波那契数列的朴素递归写法是def fib_naive(n): if n 1: return n return fib_naive(n-1) fib_naive(n-2)这个写法简洁到令人着迷但它有个致命的毛病——重复计算。fib_naive(5)会去算fib_naive(4)和fib_naive(3)但fib_naive(4)自己又会算一次fib_naive(3)。一旦n稍微大一点比如30你会发现在这个递归树里同一个子问题被反反复复计算了成千上万次。自上而下解决这个问题的思路很简单既然同一个子问题每次算出来的结果都一样那我不如开一个数组把已经算过的结果存起来下次再遇到就直接查表返回。def fib_top_down(n, memoNone): if memo is None: memo {} if n in memo: return memo[n] if n 1: return n memo[n] fib_top_down(n-1, memo) fib_top_down(n-2, memo) return memo[n]加了这么一个memo缓存时间复杂度立刻从指数级降到了 O(n)。背后逻辑就是每个子问题只算一次后续重复的路径直接“抄作业”。1.2 自下而上我从地基开始一层层盖楼和自上而下相对的是自下而上这个思路看起来更像传统意义上的“循环”。它不再把大问题递归拆成小问题而是反过来先把最小的问题边界条件解决了然后一点点往上推导直到把solve(n)算出来。同样以斐波那契数列为例自下而上的代码长这样def fib_bottom_up(n): if n 1: return n dp [0] * (n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这个写法的典型特征是没有递归调用只有for循环。它从dp[0]和dp[1]开始一步一步推导出dp[n]。这和我们平时听到的“动态规划”是同一个套路那层dp数组在动态规划里就叫“状态转移表”。1.3 两者的本质区别不是在写代码而是在选择思考顺序如果你只记住了代码模板那我可以明确告诉你过两天你面对新题目还是不会做。你要记住的是思考顺序的区别。自上而下先建立递归关系然后在递归中想办法消灭重复计算。它保留了“把大问题拆成小问题”的直觉适合用来推导状态转移方程。自下而上先确定最小状态再写循环从小到大递推。它的代码风格更接近工程化没有系统栈溢出的担忧且常数因子往往更小。在《算法很美》的课程里作者反复强调一个观点递归是你理解动态规划的第一把钥匙。你只有能把问题写成递归才能用自上而下的方式先跑通等跑通了之后你再去看代码里哪些子问题是重复的然后改进成自下而上的迭代。所以两者不是对立关系而是递进关系。2. 自上而下的“懒加载”记忆化递归到底优化了什么自上而下的记忆化递归本质上是把递归树里的重复分支裁掉。我打个比方你是一个项目经理把一个任务一层层分包下去但你在工地上立了一块黑板每个小组干完活就在黑板上记下结果。下次再有小组接到同样的任务你不是让他们重新干而是先去黑板上找答案。2.1 为什么朴素递归会指数爆炸以斐波那契为例我在网上看过很多文章讲斐波那契但大多只贴了代码没说清楚抽象逻辑。这里我带你亲手画一下递归树你就能直观感受到问题。假设n5严谨的展开过程是fib(5)要fib(4)和fib(3)fib(4)要fib(3)和fib(2)fib(3)要fib(2)和fib(1)。你发现没有fib(3)被调用了两次fib(2)被调用了三次。随着n变大这种重复量是指数级增长的。用真实数字来说话fib(40)朴素递归大约要跑十亿次加法操作我的笔记本要好几秒你如果去百度面试问fib(100)朴素递归跑到宇宙热寂也算不完。但加了备忘录之后fib(40)的耗时是毫秒级fib(1000)大概也只是瞬间。2.2 记忆化递归的标准写法套路很多初学者在写记忆化递归时总是忍不住在函数内部用全局变量或者在参数里塞一个memo字典。我建议你用下面这种标准的functools.lru_cache写法简洁又不容易出错from functools import lru_cache lru_cache(maxsizeNone) def fib_td(n: int) - int: if n 1: return n return fib_td(n-1) fib_td(n-2)lru_cache是Python标准库自带的一个装饰器它会自动缓存函数的输入输出。你在刷题时可以用它快速验证递归方程的正确性等到确定状态转移了再改成自下而上的数组版本。2.3 适用场景与隐藏缺点记忆化递归几乎适用于所有“具有重叠子问题”的递归结构。你必须确认你的递归子问题之间有重叠如果完全没有重叠那加缓存不仅没用还会平白消耗额外内存。它在工程中有一个不可避免的缺点递归深度。Python默认递归深度是1000层左右你如果处理n2000的题目即使加了缓存也会直接栈溢出。这时候你就必须在递归里手动调sys.setrecursionlimit(1000000)或者干脆换自下而上实现。让我给你一个判断标准如果这道题的n能到10的5次方以上我基本会放弃自上而下直接写自下而上。面试时这样做不但能避免栈溢出还能向面试官展示你的代码具有更好的工程鲁棒性。3. 自下而上的“迭代宇宙”从底到顶的极致优化如果说自上而下是“解决问题”自下而上更像是“构建答案”。它和数学归纳法简直是一个模子刻出来的先证明基础情况成立再证明如果第 i 步成立那么第 i1 步也成立最后得出结论所有情况都成立。3.1 从记忆化递归到递推表格状态转移方程的诞生自下而上的代码核心就是一个状态转移方程。我们把解决这个问题的“每一个规模的解法”存在数组里然后通过相邻项的关系从已知项推导出未知项。拿爬楼梯问题来说你每次可以爬1级或2级问到达第n级楼梯有多少种爬法。这个问题的递归直觉特别明显你要到第n级只能从第n-1级迈1步或者从第n-2级迈2步。所以方案数等于f(n-1)f(n-2)。自下而上的解法把这句话翻译成数组遍历def climb_stairs(n: int) - int: if n 2: return n dp [0] * (n1) dp[1] 1 dp[2] 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这里的dp[i]就代表着“到达第 i 级楼梯的方法数”。这个写法和你刚学时的fib_top_down结论一致但底层完全不一样——它没有进行任何函数调用就是纯粹的数数相加。3.2 空间优化滚动数组不能只背模板刷过几道题的读者都知道很多自下而上解法可以优化空间把 O(n) 的数组压成 O(1)。但有一种误区我必须提醒你并不是所有动态规划都适合滚动数组。只有当前状态只依赖前一个或者前两个状态时这个优化才成立。对于斐波那契这种依赖前两项的简单递推滚动数组就是三个变量不断交替def fib_space_optimized(n: int) - int: if n 1: return n prev2, prev1 0, 1 for _ in range(2, n1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1使用滚动数组之后内存占用从 O(n) 降到了 O(1)。有时候这种空间压缩在大数据量场景里就是能否跑过超时判定的决定性因素。3.3 当自下而上比自上而下慢稀疏问题直觉看到这一节的小标题你可能会愣一下难道自下而上还会比记忆化递归更差答案是可以的。假设你的状态空间虽然是n但真正能达到的状态非常稀疏比如n可能很大但你只需要求解其中10个状态。记忆化递归因为“懒”不会触碰不需要计算的状态而自下而上会老老实实从0循环到n把整条状态链全算一遍。所以我个人在实际刷题时有个习惯先判断这个递推是稠密型还是稀疏型。如果子问题的种类远远少于问题规模我就会倾向用lru_cache这种自顶向下的写法省掉大量无效计算。4. 正面交锋两者在性能、工程、编码难度上的深度对比文章写到这里应该摆出一张对比表把两者的特点列清楚。很多工程师喜欢把这当成“背概念”但我们不如把它当成“选型指南”。维度自上而下记忆化递归自下而上递推数组思考方式从大问题拆到小问题从小问题推到大问题代码风格递归缓存逻辑更接近状态转移方程的推导循环数组逻辑更贴近最终实现时间复杂度通常 O(n)但可能引入字典查询哈希开销通常 O(n)常数因子更小性能更稳定空间复杂度系统栈 O(n) 缓存 O(n)数组 O(n)且可优化为 O(1)栈溢出风险高递归深度有限制低使用循环不会爆栈适用场景状态转移方程难推导、稀疏状态、快速验证想法状态稠密、大规模计算、对性能/内存敏感的工程场景从表述里就能看出我的倾向面试时我一般先写自上而下因为思考负担小、不容易出错等确认了状态转移方程再和面试官讨论优化改写成自下而上。这个流程符合正常人的认知规律也能体现你具备从“能跑”到“跑得漂亮”的优化意识。4.1 为什么很多面试官更喜欢你写自下而上我跟不少大厂面试官交流过他们普遍有一个共识自上而下的写法虽然正确率高但它把一些本该由你思考的复杂度评估问题“藏”在了递归栈里。而自下而上的写法会让你在定义dp[i]的时候就梳理清楚规模、状态含义、边界条件三大要素逼迫你深刻理解问题本质。说个真实的场景面试题是0-1背包问题。候选人三分钟写出记忆化DFS版本跑通用例面试官往往会追问一句“如果你不用递归怎么用循环实现”如果只能答出“用双层循环但说不清背包容量和物品顺序”那这道题的印象分是会打一点折扣的。所以我建议技术文章阅读者不仅要把自上而下当“快速验证工具”还要能在5分钟内心算自下而上的边界条件。这两个能力是你玩转动态规划的基础功。4.2 关于复杂度的终极误区别只背O(n)我在牛客网看过不少人背模板问fib的复杂度脱口而出“O(n)”。这其实只对了一半完整回答还要包括空间复杂度。更有意思的是很多人没意识到自上而下的记忆化递归时间虽然是 O(n)但哈希表查找带来常数开销可能比自下而上的数组访问高出一到两倍。所以如果你要处理的是上百万数据的真实工程自下而上几乎是我唯一的选择。这个速度差异不是算法复杂度级别差而是工程落地时的性能和资源占用差。5. 动手实战用两种思路手撕三个经典递归问题光说不练假把式。接下来我用两个经典算法题分别演示自上而下和自下而上的完整实现。这两道题都来自LeetCode高频题库也是《算法很美》系列反复提到的模型。5.1 案例一最小路径和——真正理解“子问题”重叠经典题目给定一个m x n的网格每个格子有一个非负整数你从左上角到右下角每次只能向右或向下求路径上的最小数字总和。这道题卡过不少初学者原因就是二维数组的递归关系比一维的要抽象一点。我们拆解逻辑你到达(i, j)的路径必定来自左边(i, j-1)或者上边(i-1, j)。所以到达(i, j)的最小路径和 当前格子值 两者中较小的那个。自上而下记忆化递归def min_path_sum_td(grid): m, n len(grid), len(grid[0]) memo {} def dfs(i, j): if (i, j) in memo: return memo[(i, j)] if i 0 and j 0: return grid[0][0] if i 0 or j 0: return float(inf) memo[(i, j)] grid[i][j] min(dfs(i-1, j), dfs(i, j-1)) return memo[(i, j)] return dfs(m-1, n-1)这写法核心就是“从终点倒推”。递归关系清晰边界由inf挡掉非法路径。自下而上递推def min_path_sum_bu(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]自下而上的写法是“从起点正推”一段段填满二维数组。追根溯源你会发现这两个写法的复杂度都是 O(m*n)区别只在推导顺序。5.2 案例二编辑距离——状态转移方程怎么推、怎么写编辑距离在动态规划里可以说是个分水岭能独立把它写出来说明你已经真正理解了DP。题目要求给你两个单词word1和word2每次操作可以插入、删除、替换一个字符问把一个单词变成另一个的最少操作次数。我们定义dp[i][j]为“把word1的前 i 个字符变成word2的前 j 个字符所需的最少操作数”。递归关系分两种情况当前字符相同dp[i][j] dp[i-1][j-1]当前字符不同dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])这里我不打算贴全部代码只重点说一个思维陷阱很多人分不清dp[i-1][j]和dp[i][j-1]分别对应删除还是插入。你只要抓住“状态是已处理的字符前缀”这一点就不会绕晕。自上而下写这个题时边界条件非常容易出错当i0时dp[0][j]只能靠j次插入完成当j0时只能靠i次删除完成。这些边界条件在自下而上里提前初始化在自上而下里用if判断处理两条路殊途同归。5.3 关于递归的“钥匙”汉诺塔和其他纯递归问题当然递归不只是动态规划的自上而下。汉诺塔就是另一个经典代表。汉诺塔里没有重叠子问题没有备忘录的用武之地但它完美展示了自上而下的拆解思想你要把 n 个盘从A移到C先把上面 n-1 个盘从A移到B再把最大的盘从A移到C最后把 n-1 个盘从B移到C。这个过程没有自下而上的等价的迭代写法它天然就是一个“递归分治”模型。这就是我在文章开头说的自上而下更像拆分思维本身而自下而上则偏向合并和递推思维。6. 从递归出发它如何渗透到算法全家桶递归看着只是一块砌墙的砖但它的地位恰恰像砖之于大厦。掌握递归不是会写一两个函数那么简单它是你通向深度优先搜索、动态规划、分治算法、回溯算法乃至一些现代机器学习算法的钥匙。6.1 DFS、回溯与递归血浓于水深度优先搜索DFS在树和图中的实现方式就是递归。回想二叉树的前序遍历你写preorder(node.left)再preorder(node.right)这不就是标准的自上而下吗回溯算法里的“选择—递归—撤销选择”模板本质上也是在递归的框架里加上状态回溯。如果你能把自上而下递归里“当前层做什么、子问题传什么”想明白你写DFS、回溯就会非常顺手。很多人觉得树的题难其实不是树难而是对递归控制的“递”和“归”两个阶段没有体感。6.2 分治算法的基因也是递归归并排序、快速排序它们在代码形式上就是递归。分治可以拆成三步分解、求解、合并。这三个步骤几乎就是自上而下递归的骨架。你学会了递归再去啃这些排序算法会发现只是把斐波那契的“加法合并”换成了“数组合并”而已。6.3 强化学习里的“时间差分”和“自举”我看到热搜词里有强化学习算法、PPO算法如果有人觉得递归实在学不进去我可以给你提供一个高级动力——强化学习里的时序差分TD更新它在逻辑上和动态规划的自举思想是通的。TD_target r gamma * V(s)这个公式本质上就是利用下一步的状态价值去更新当前步状态价值这和斐波那契里dp[i] dp[i-1] dp[i-2]的自下而上递推逻辑是一致的。你一旦把自上而下/自下而上这套认知框架带进强化学习理解Bootstrapping就不会那么费劲。这也是为什么算法底子好的人接触新领域总是很快——因为底层的核心思维是相通的。6.4 递归思维的真正训练法从“照葫芦画瓢”到“肌肉记忆”文章最后我想给你一个可以照做的训练计划。很多初学者收藏了几百个模板还是做不出题原因在于输入输出看了就忘。我建议你按下面这个流程练先画递归树拿到题先在纸上写递归关系别急着敲代码。用具体小规模例子手动展开一层确认子问题是否重叠。写自上而下用lru_cache快速把递归跑通验证思路。改自下而上把递归改成循环数组注意边界条件。尝试空间优化看当前状态依赖的是哪几个历史状态尝试滚动数组。这套流程我称之为“递归四步走”。我带过的实习生只要老老实实按这个顺序刷完20道树和DP题递归基本就再也不会成为心理障碍。递归的核心不是天赋而是你脑海中对“递去”和“归来”两个方向的掌控力。递归是算法的灵魂之一。自上而下给了你快速上手的入口自下而上给了你落地性能的出口。两个方向你都值得熟练掌握。