很多人学递归时都会背那几句口诀——“递归要有终止条件”“递归就是自己调用自己”“递归要有递推关系”。然后一到写代码就卡壳汉诺塔看懂了换个题目就不会全排列看懂了遇到重复元素又懵了。其实问题不在你笨在于大多数教程只讲了递归的“形态”没讲清楚递归的“思路是怎么长出来的”。这篇东西我打算用汉诺塔、全排列、整数划分这三个经典题目把递归从“背模板”拉到“自己会推”的程度。不管你是刚学数据结构的学生还是工作中突然要用到递归的开发者只要愿意耐着性子读完、动手敲一遍代码之后就再也不会怕递归题了。1. 递归的本质不是“自己调用自己”这个表面规则1.1 问题变小的路径才是递归的灵魂递归的教科书定义是“函数直接或间接调用自身”这个说法没错但很容易误导人。按照这个定义只要写一个函数末尾调用自己就等于“用了递归”真正的递归核心在于把一个规模为n的问题转化成规模更小、但结构相同的问题一直转化到规模小到可以直接解决为止。举个生活化的例子。你在电影院想知道自己坐在第几排但又懒得一排排数。你可以问前面的人“你是第几排”前面的人也不知道他只能再问他前面的人。一直到第一排那个人说“我是第一排”答案再一个个传回来第二排、第三排……最终你知道了自己是第几排。在这个过程中每个“问前面的人”的动作都是同一件事求自己这一排的编号等于前面一排的编号加1。第一排的人不再问别人直接给出答案这就是终止条件。计算机里的递归本质就是这个过程。函数体里调用的不是“怀里的自己”而是“规模更小的自己”。判断递归写法对不对不要只看有没有自己调用自己而要问一个问题我这个函数每调用一次问题的规模是不是确实变小了变小之后的子问题跟原问题是不是同一个性质两个条件都满足递归才走得通缺了任何一个要么死循环要么根本算不出正确结果。1.2 递归在计算机里如何运转栈帧与调用栈很多人学递归会疑惑我明明没有改任何变量的值为什么递归返回之后上一层函数里那些变量还是原来的值这是因为每一次函数调用计算机都会为它分配一块独立的栈帧stack frame局部变量、参数、返回地址都存在栈帧里。递归调用n次就有n个栈帧一层层压上去像叠盘子一样。最底层的那一个栈帧对应的是触发终止条件的那个调用它执行完返回后系统弹出这一层栈帧把结果交给上一层上一层用自己的栈帧接着算算完再返回……这个“后进先出”的顺序决定了递归天然具备一种“先深入再回溯”的执行节奏。也就是说你在递归函数里定义一个局部变量step不管递归了多少层每一层都有自己的step互不干扰。这也是为什么递归代码看起来“什么都没保存”却能在返回后保留当时的现场。理解这一点后面写全排列的回溯就会非常顺畅——你修改的必须是共享状态比如used数组、全局路径局部变量反而通常不需要恢复。1.3 递归与循环其实是一枚硬币的两面任何递归都能改写成循环任何循花都能改写成递归这是计算机科学里的基本结论。区别在于循环是“明着”把状态保存在变量里递归是“暗着”把状态保存在系统栈帧里。那为什么还需要递归因为有些问题用循环写需要自己维护一个栈、自己规划状态复杂且容易出错而递归的结构天然与问题的数学结构一一对应代码简洁、可读性高。比如二叉树的遍历递归三行写完迭代要写一个复杂的显式栈循环。反过来如果某个递归会递归几万层系统栈不够用那就得考虑改成循环。所以递归和循环不是对立关系而是“选哪个更方便”的关系。这个平衡后面第六部分细讲。2. 汉诺塔递归第一个真正“杀”我脑子的问题2.1 三根柱子与n个盘子的状态演变汉诺塔的规则想必大家都听过有三根柱子A、B、CA柱上从上到下从小到大叠了n个盘子目标是把所有盘子移到C柱每次只能移动一个盘子任何时候大盘子不能压在小盘子上面。我第一次见到这道题时尝试用手去模拟n3的每一步感觉还挺简单但想到n64脑子里就炸了。后来才发现汉诺塔这道题恰恰是递归的“天然试验场”因为它不需要你想清每一步具体怎么移只需要你区分“整体搬运”和“单独移动”。要把n个盘子从A搬到C你可以这样拆解先把A上面的n-1个盘子看作一个整体借助C柱从A搬到B。这一步实际上是一次规模为n-1的汉诺塔问题。把第n个大盘子直接从A搬到C。这一步只需要一次移动。再把B上的n-1个盘子看作整体借助A柱从B搬到C。这又是一次规模为n-1的汉诺塔问题。把“把x个盘子从source搬到target借助auxiliary”这个动作用函数hanoi(n, source, target, auxiliary)表示上面的思路立刻变成代码def hanoi(n, source, target, auxiliary): if n 1: print(fMove disk 1 from {source} to {target}) return hanoi(n - 1, source, auxiliary, target) # 先把上面 n-1 个搬到辅助柱 print(fMove disk {n} from {source} to {target}) # 最大盘直接到目标 hanoi(n - 1, auxiliary, target, source) # 再把这 n-1 个搬到目标柱注意第三行和第五行hanoi的参数顺序变了第一行递归的target和auxiliary换了位置因为它要把盘子搬到辅助柱而非目标柱第二次递归则是把辅助柱当成新的源。好多人在这一步踩坑——照着别人代码抄抄完发现参数交换不理解下次换个参数名就写错。建议把参数名改成语义更强的src, dst, tmp来写提醒自己“每层递归的三根柱子身份都在变化”。2.2 移动次数的递推公式与O(2^n)的现实意义汉诺塔不只是能“移动完”就行面试里经常追问n个盘子到底要移动多少次从上面递归结构可以直接推出递推公式。设T(n)表示移动n个盘子所需步数。按照三步走搬n-1个盘子到辅助柱需要T(n-1)步搬最大盘到目标柱需要1步再把n-1个盘子从辅助柱搬到目标柱又需要T(n-1)步。所以T(n) 2 * T(n-1) 1 T(1) 1这个递推怎么解可以多列几项找规律T(1)1, T(2)3, T(3)7, T(4)15很眼熟T(n) 2^n - 1。严谨一点也可以用数学归纳法证明假设T(k) 2^k - 1那么T(k1) 2*(2^k-1) 1 2^(k1) - 1成立。这个公式值得好好品一下。n64的时候2^64 - 1 18446744073709551615大约1.8乘以10的19次方。假设你每秒钟移一个盘子一年大约31536000秒算下来要超过5800亿年才能移完。它告诉我们递归虽然代码简洁但“简洁”不等于“高效”指数级增长是非常恐怖的事情。这也是为什么“汉诺塔非递归”是经典面试题——你要是连指数复杂度都没意识到优化更是无从谈起。2.3 从三柱到四柱多递归参数的扩展很多同学学完三柱汉诺塔看见“四柱汉诺塔”又慌了。其实思路没变还是“分整体一步步搬”只是多了一根可以用的柱子选择性变多了。四柱时不能简单套三柱的公式。四柱问题是这样的A柱上有n个盘子B、C、D三根空柱子都可以作为辅助目标全部移到D。我们的策略可以调整为把上面x个盘子从A搬到B借助C、D两根辅助柱这是规模x、四柱环境下的子问题把A上剩下的n-x个盘子从A搬到D此时只能借助一根辅助柱因为B上有盘子不能压——这就是一个三柱汉诺塔问题了再把B上x个盘子搬到D借助A、C两根辅助柱又一个四柱子问题。设四柱问题的步数为F(n)三柱问题步数为T(n)则有F(n) min( 2 * F(x) T(n-x) ), 其中 1 x n取最小值是因为我们需要试不同的x找到把n个盘子搬完的最优拆法。这个式子叫做Frame-Stewart算法目前仍是“猜想最优性”级别的问题还没人证明它一定最优但实际表现非常好。写代码时你可以用一个循环枚举x递归里分别计算F(x)和T(n-x)再记录最小值。四柱问题极具代表性因为它告诉我们递归的参数数量、辅助柱数量都不是死的完全可以根据问题场景增加维度。学会三柱汉诺塔之后四柱、五柱都只是“多开几个参数”的事。3. 全排列递归中的“选择-递归-撤销”三步节奏3.1 把排列问题转化为位置决策问题全排列的题目长这样给定数组[1, 2, 3]输出所有可能的排列123, 132, 213, 231, 312, 321共6种。很多人拿到题第一反应是“把所有数字随便组合一下”可真写起来就发现怎么保证不重复、不遗漏递归解法里通常走一条更清晰的路线把“排列”看成“往n个空位里填数字”的过程。第一个空位可以填任何一个数字第二个空位可以填剩下的数字依此类推。每填一个位置问题规模就缩小1从“填n个位置”变成“填n-1个位置”而“填n-1个位置”的规则和原问题一模一样只是候选数字少了一个。这就构成了标准的递归结构。用代码表达核心是这样几步path记录当前已经填好的排列used数组标记哪些数字已经用过递归函数接受“当前要填第几个位置”作为参数遍历所有数字如果没用过就填入path标记used递归下一层然后撤销used标记并把数字从path末尾弹出。这样每个排列都会被且仅被构造一次因为每个位置都试过所有可能的数字并且用used保证排列内数字不重复。def permute(nums): res [] path [] used [False] * len(nums) def backtrack(): if len(path) len(nums): # 所有位置填满了记录结果 res.append(path[:]) # 注意这里要复制一份 path return for i, num in enumerate(nums): if used[i]: continue used[i] True path.append(num) backtrack() # 填下一个位置 path.pop() # 撤销 used[i] False backtrack() return res我在初学最常犯的错是直接把path塞进res而不是path[:]。因为path是引用类型后面pop()会随时修改它如果不复制最终res里存的十几个列表全指向同一个对象。这是Python写回溯的经典坑务必记住。3.2 手推一遍三个元素的全排列为了搞懂回溯为什么能“不重不漏”动手推一遍是最快的。就拿[1, 2, 3]来说第一层要填path[0]。从1开始把1放入pathused[0]True进入第二层。第二层要填path[1]。从1开始发现used[0]True跳过看2可用放入path进入第三层。第三层要填path[2]。1、2都不可用3可用放入path。此时path长度等于3记录[1,2,3]。返回第三层末尾弹出3used[2]False第三层循环结束返回第二层。第二层继续循环3可用放入path进入第三层。第三层此时只能填2记录[1,3,2]。返回后弹出2再返回第一层。第一层循环到2同样套路产生[2,1,3]、[2,3,1]再到3产生[3,1,2]、[3,2,1]。整个流程像一个树状的搜索每一层代表一个位置每条分支代表一个可选的数字叶子节点就是完整排列。回溯之所以叫“回溯”是因为你“走”到一条分支尽头后要退回到上一个岔路口尝试另一条分支。“分支选数字”这个动作就是递归里的“选择”“退回来清空状态”就是“撤销”。这是所有回溯类问题——组合、子集、N皇后——共通的骨架。3.3 去重与顺序保证边界条件的处理如果数组里有重复元素比如[1, 1, 2]直接套上面的代码会输出两套一模一样的排列。原因很简单两个1在数组里位置不同但作为“值”是相等的系统会把“第一个1在前第二个1在后”和“第二个1在前第一个1在后”当成两种填法。去重思路需要先对数组排序让相等的数字挨在一起然后在每一层循环里规定如果当前数字和前一个数字相同且前一个数字还没有被用过就跳过当前数字。有人会问为什么不看前一个用过没有举例子就容易懂了。在第一层如果用第一个1不需要管用第二个1时会发现前一个1没有被用过——因为它在第一层循环里被跳过了——于是第二个1也会被跳过保证每一层相同值只尝试第一次出现的那一次。而如果前一个1已经被用过说明这是“在同一分支里重复了两次相同值”此时位置不同属于合法排列不应该跳。这个条件写出来是if i 0 and nums[i] nums[i-1] and not used[i-1]: continue顺序保证上如果你希望输出按字典序排列其实只要初始数组有序回溯的遍历顺序自然就是字典序的。这两个细节合起来就是“去重回溯”的完整写法。不去重时时间复杂度是O(n!)集合去重后依然是O(n!)但剪枝可以减少实际开辟的递归分支数量对性能有实质帮助。4. 整数划分递归里的“拆分”思维与重叠子问题4.1 整数划分到底在拆什么第三个经典问题是整数划分。题目是把一个正整数n拆成若干个正整数之和不考虑顺序问总共有多少种拆法。比如n4可以拆成431222111111一共5种。注意31和13算同一种因为不考虑顺序这也是整数划分比“排列数”难下手的原因你没法简单地把数字填进位置因为位置根本没有意义。那递归怎么定义关键一步是引入“最大加数不超过m”的限制。设f(n, m)表示把n拆成若干正整数之和且每个加数都不超过m的方案数。为什么需要这个限制因为如果不加限制递归时可能产生重复组合。加上“最大加数不超过m”就能保证每一步拆出来的数字永远都不大于前一个形成一种自然的大小顺序从而避免重复。4.2 递推关系的建立与边界讨论接下来推递推式。所有合法拆分按照“是否包含一个大小为m的加数”分成两类逻辑上刚好把集合分成互不相交的两部分包含加数m既然包含了一个m剩下的部分就是把n-m拆成每个加数都不超过m的方案数也就是f(n-m, m)。不包含加数m所有加数都不超过m-1也就是f(n, m-1)。所以递推式是f(n, m) f(n-m, m) f(n, m-1)边界条件需要想清楚。当n 0时只有一种拆分什么都不拆。这看起来有点怪但必须定义为1否则递推没法收敛。当m 0且n 0时不可能用不超过0的数拆出正整数n所以方案数为0。还有一个隐含边界当m n时“最大加数不超过m”和“最大加数不超过n”等价因为拆分n时根本不可能用大于n的加数。因此可以加一步剪枝if m n: return f(n, n)可以省掉不少递归分支。写出来就是这样def partition_count(n, m): if n 0: return 1 if m 0: return 0 if m n: return partition_count(n, n) return partition_count(n - m, m) partition_count(n, m - 1)把n4, m4代入试算f(4,4)拆成f(0,4)f(4,3)一路推下去会得到5和上面手写一致。我第一次手推时完全跟不上直到画了一张递归树才明白每往下走一层要么减少n要么减少m两个参数都在严格变小所以递归一定能在有限步内结束。这种“参数严格递减”的论证方式以后判断自己写的递归会不会死循环也是同一个套路。4.3 从递归到记忆化搜索、再到DP的思想跃迁整数划分和汉诺塔、全排列不同点在于它的子问题重叠非常严重。比如算f(4,4)会调用f(3,3)算f(5,4)也会调用f(3,3)吗会。如果不做任何缓存同一个参数会被递归计算非常多遍。给n稍大一点比如n50纯递归会慢得让人怀疑电脑死机。解决办法就是记忆化把已经算过的(n, m)结果存下来下次直接用。Python里可以用lru_cachefrom functools import lru_cache lru_cache(maxsizeNone) def partition_count(n, m): if n 0: return 1 if m 0: return 0 if m n: return partition_count(n, n) return partition_count(n - m, m) partition_count(n, m - 1)加了缓存以后每个(n, m)只算一次复杂度降到O(n*m)。再进一步观察递推式你会发现它跟自底向上的动态规划是同一张表用二维数组dp[n][m]存结果从小到大填表逻辑完全相同。所以整数划分这道题完美的展示了“递归 → 记忆化 → 动态规划”的思想递进。很多人上来就背DP的状态转移方程背得云里雾里但是从递归推过来每一步都清清楚楚。这就是为什么我在文里反复强调“先写递归再优化”这条路。5. 递归三板斧与可复用模板我反复踩坑后沉淀的写法5.1 终止条件不是“随便写一个”大量递归Bug出在终止条件上。写之前请问自己三个问题当输入规模小到什么程度时答案不再需要递归这个最小问题的答案应该是什么递归过程中有没有可能永远到不了这个最小输入对于汉诺塔最小时n 1答案是一句话“直接移动”。对于全排列最小时是“所有位置都填满”此时它是一个合法结果要记录。对于整数划分最小时是n 0或m 0分别对应1和0。规则很简单但很多人在全排列里忘记写if len(path) len(nums)或者把等于号误写小于号结果要么爆栈要么漏结果。终止条件最稳妥的检查办法是从n1开始手动推一层看是否符合预期再检查n2能不能由它推出来。如果这两个都能过基本就不会因终止条件出问题。5.2 递推公式背后的不变量递推公式的建立本质是回答“为什么大规模问题可以被拆成小规模问题”。好的递推式子一定要有一个“在每次递归中保持不变的东西”。漢诺塔的不变量是“规模是n的问题等价于两次规模n-1的问题加上一次移动”全排列的不变量是“填完当前位置后剩余问题依然是填一个更短的排列”整数划分的不变量是“最大加数限制使得划分不重复”。我见过很多人递归写不下去不是不会写代码而是压根没有找出这个不变量。所以以后拿到题目先别急着敲键盘试着在纸上写一句话“规模为n的问题等于……规模为n-1或n-k的问题的组合它们的规则跟原问题一样”。写得出这句话递归函数的结构其实已经定了八九成剩下全是机械操作。5.3 回溯时的状态恢复剪枝前的最后一关只要递归里修改了“跨越多个递归层次共享的数据”就必须在递归返回后恢复原状。最典型的共享数据是used数组等同层标记path、temp这类正在构造的结果容器全局计数器或全局全局状态变量。恢复时机也很固定在递归调用之后立刻恢复。有些同学把恢复写在递归函数末尾如果是尾递归那问题不大但如果递归后面还有别的逻辑恢复写晚了第一层看到的状态已经被下一层修改了结果必然出错。另外一条铁律是往结果列表里添加当前结果时必须复制一份副本。上面全排列里的res.append(path[:])就是这个原因。至于局部变量它们天然隔离在每一层栈帧中不需要恢复——但你如果图省事把局部变量换成全局变量就给自己埋了雷。这套“选择-递归-撤销”模板稍微改改就能覆盖组合总和、子集、N皇后、括号生成等一大批回溯题。建议把它写进自己的代码笔记里当作肌肉记忆来练。6. 递归调优与“递归改迭代”的实战路径拿快速排序非递归说事6.1 深递归会踩到的栈溢出递归代码虽然漂亮但有一个致命弱点递归深度受系统栈限制。Python默认递归深度只有1000层超过就会抛RecursionError。你可以用sys.setrecursionlimit把上限调大但这是“掩耳盗铃”系统给你的是真实的内存限制调大上限可能直接触发进程崩溃。所以写递归前最好估一下深度。二分递归深度是O(log n)问题不大链表反转这类递归深度是O(n)n到1万就危险了。快速排序如果每次都能选到中位数递归深度是O(log n)但最坏情况深度是O(n)大数组用递归实现快排极端情况下同样会爆。我自己就有过在数据量稍大的生产环境里写递归快排直接栈溢出崩溃的经历后来老实改成非递归实现。6.2 记忆化算过的不要重复算如果递归是“自顶向下”的同一组参数可能被反复计算。拿斐波那契数列举例纯递归算fib(40)慢到怀疑人生因为重复调用的次数是爆炸级别的。解决办法在前面整数划分里已经演示过了“给递归函数加一个缓存键是决定结果的参数组合值是算好的结果”。Python里最简单的是functools.lru_cache其它语言可以手写一个哈希表。要注意的是记忆化只对“同一个参数组合的结果相同”的问题有效。像汉诺塔这种每一层都要输出移动过程的问题单纯缓存移动次数可以但缓存整个移动序列就不一定合适而全排列的每个结果都不同记忆化根本用不上。所以记忆化是“锦上添花”不是“万能药”用之前先确认问题是否具备重叠子问题的性质。6.3 如何用显式栈把递归改成迭代递归改迭代最通用的方案就是“用手动栈模拟系统调用栈”。思路分三步确定递归函数里影响执行的参数集合比如快速排序里的左边界和右边界每遇到一次递归调用就把对应参数压入栈中用while循环不断弹栈执行当前任务并把新的子任务压下直到栈空。快速排序的非递归版本非常经典正好回应很多人在搜的“快速排序非递归”。用递归写快排核心是三行def quick_sort(arr, left, right): if left right: return pivot partition(arr, left, right) quick_sort(arr, left, pivot - 1) quick_sort(arr, pivot 1, right)改成显式栈就是把左右边界压栈def quick_sort_iterative(arr): stack [(0, len(arr) - 1)] while stack: left, right stack.pop() if left right: continue pivot partition(arr, left, right) stack.append((left, pivot - 1)) stack.append((pivot 1, right)) return arr注意栈的入栈顺序不影响正确性但会影响执行路径。这里先压左边再压右边弹栈时就会先处理右边。效率上显式栈和系统栈没有本质差异只是你不再受Python递归深度限制而且可以随时中途终止、保存现场可控性更强。这类手法不只用于快排。二叉树的先序非递归遍历、汉诺塔的非递归实现都是同一个套路。我个人的建议是如果递归深度不会超过几百层而且问题天然递归结构清晰优先写递归代码好读如果数据规模大、深度不可控果断换非递归。两条路都会写才算真正掌握了递归而不是只会背模板。最后再分享一点个人体会。很多人学递归最大的心理障碍是“递归到底是怎么想出来的”。我自己的经验是别急着从代码层面想先把自己变成递归函数。遇到汉诺塔就假装自己是那根柱子旁边搬盘子的指挥者遇到全排列就当自己在填一张有n个空格的彩票。想清楚“我把规模缩小了一步剩下的是不是一模一样的问题”递归这条线就连起来了。学完这三个经典之后再去碰树的遍历、图的搜索、动态规划你会发现它们身上都有这三种递归的影子。到那时候递归就不是背出来的知识而是你工具箱里一把随时能用的刀了。