递归这个东西很多人学算法的时候一开始就卡在这里。不是看不懂递归的代码而是看不懂递归的执行过程。每次看到一个函数调用自己脑子里就绕成一团浆糊。其实这个系列前面铺垫的递归入门内容核心就一句话递归不是“自己调用自己”这么简单而是把一个大规模问题拆成同样结构的小规模子问题由函数自己去处理子问题再把子问题的结果合并成当前问题的答案。这个系列选了五道题来打通这个认知前两题是斐波那契、汉诺塔这类入门例子这次要聊的3、4、5题——反转链表、两两交换链表中的节点、快速幂正好是从“结构型递归”跨到“计算型递归”的关键三道。我强烈建议准备算法面试的朋友、正在学数据结构与算法的大学生、以及想彻底搞懂递归本质的开发者都认真把这三道题吃透。它们表面上是三道不同的题实际上共用同一套递归心智模型。1. 先弄懂递归的“递”和“归”到底是怎么回事1.1 递归三要素终止条件、子问题拆分、回溯处理很多教程讲递归会列出一堆术语递归基、递推关系、栈帧、回溯。听着吓人但落地就三个问题什么时候停子问题是什么拿到子问题的结果之后怎么处理我习惯叫它“递归三问”。第一问是终止条件也叫递归基。这是递归函数里第一个要写的判断没有它函数就会无限调用直到栈溢出。第二问是子问题拆分也就是“我怎么把一个规模为n的问题变成规模为n-1或者n/2的问题”。这里的关键在于子问题和原问题必须是同构的只是规模更小。第三问是回溯处理这是最容易被忽略的一步。很多人写完终止条件和递归调用就以为完事了结果返回上去的数据是错的。回溯处理指的是当递归调用返回之后当前这一层还需要做点什么才能把子问题的答案组装成当前问题的答案。拿剥洋葱来类比。你要把一整颗洋葱剥到只剩葱心剥掉第一层皮之后剩下的还是一颗洋葱只是小了一圈。这就是子问题同构。剥到最里面那一层不能再剥了这就是终止条件。而你剥完整个洋葱之后把皮重新一层层穿回去的过程就是回溯处理。递归的代码之所以难读就是因为“剥”的过程是顺着调用栈往下走的而“穿回去”的过程是在调用栈返回时逆着往上走的两个方向相反脑子里要能同时模拟这两条路径。1.2 为什么这三个题能打通递归的任督二脉选题是有讲究的。反转链表和两两交换节点都属于“链表递归”它们利用的是链表天然具有的递归结构——一个链表由一个头节点和一个更短的子链表组成。这种结构让“子问题拆分”变得特别直观我先把头节点摘出来剩下的就是一个规模更小的同类问题。而快速幂属于“数值计算递归”它不再有节点和指针而是纯粹通过数学公式把指数拆分。做完这三道题你会发现递归不只能处理“结构型”问题还能处理“计算型”问题抽象能力明显上了一个台阶。这三个题的难度梯度也很舒服。反转链表是典型的“递归回溯”模板代码极短但每一步都有讲究两两交换链表节点相当于在反转链表的基础上加了一个“分组”的概念子问题的边界更值得琢磨快速幂则把递归的时间复杂度从O(n)降到了O(logn)让你看到递归结合分治思想之后的威力。顺序做下来你对“递”和“归”的感知会非常具体。2. 第3题反转链表——递归版与迭代版的双线对照2.1 反转链表到底在反转什么题目描述很简单给一个单链表的头节点 head反转链表返回反转后的新头节点。比如 1-2-3-4-5 变成 5-4-3-2-1。先明确一个关键点链表反转不是把节点的值改掉而是把每个节点的 next 指针方向翻转。也就是说节点还是那些节点但原来指向后一个的指针现在要指向前一个。这一点想清楚后面所有的步骤都是围绕指针变化来的。迭代解法是最直观的。用三个指针 prev、cur、next 遍历链表cur 是当前要处理反转的节点prev 是 cur 的前一个节点初始为 Nonenext 是 cur 的原后继节点防止改完指针后丢失。每一步操作就是让 cur.next 指向 prev然后整体往右挪一格。循环结束时 cur 为 Noneprev 正好指向最后一个节点也就是反转后的新头。这个解法空间O(1)时间O(n)是工程上最常用的写法。但很多人只背了迭代代码对递归版的理解一直隔着一层纱。2.2 递归解法让子链表先反转再处理当前节点递归版的代码很短但每行都值得细品def reverseList(head): if head is None or head.next is None: return head new_head reverseList(head.next) head.next.next head head.next None return new_head先回答三问。终止条件当前节点为空或者当前节点只有一个节点。因为空链表不需要反转只有一个节点的链表反转之后还是它自己直接返回。子问题拆分head.next 开头的这一段子链表它本身也是一条链表反转它就能得到“除去头节点之外的剩余部分的翻转结果”。回溯处理这是最精彩的两行。head.next.next head让原来 head 的下一个节点反过来指向 head。head.next None则是斩断 head 原来向后的指针。我用一个3节点链表实际走一遍。链表是 1-2-3。调用 reverseList(1)发现 head.next 不为空于是调用 reverseList(2)。同样reverseList(2) 调用 reverseList(3)。到 reverseList(3) 时head.next 为 None满足终止条件返回节点3。现在回到 reverseList(2) 这一层new_head 传入的是 reverseList(3) 的返回结果也就是节点3。执行 head.next.next head此时 head 是节点2head.next 是节点3这行代码等价于 3.next 2于是变成了 2-3-2 的局部环。下一行 head.next None把 2-3 这条指针断掉链表变成 3-2。返回 new_head节点3。再回到 reverseList(1) 这一层new_head 收到的是节点3。head.next 是节点2于是 head.next.next head 等价于 2.next 1链表变成 3-2-1-2 的局部环。head.next None 把 1-2 断开。最终得到 3-2-1返回节点3。整个过程里new_head 一直指向节点3这个节点是反转后真正的新头节点自始至终没有被改变过。2.3 递归版易错点与迭代版对照这个题我在实际带人的时候发现几个特别常见的错误。第一个错误是把head.next.next head写成head.next head。这是完全不同的两件事。前者是“让后继节点指回我”完成的是反转的核心动作后者是“我自己指向自己”会让链表直接形成一个环。第二个错误是漏掉head.next None。如果不斩断原来的正向指针在返回之后链表会出现环最终导致遍历时死循环。第三个错误是把终止条件只写成head is None漏掉head.next is None的情况。这样当链表只有一个节点时代码会继续往下走head.next为 None执行head.next.next直接抛空指针异常。迭代版和递归版的核心区别在于是否显式维护 prev 指针。迭代版用 prev 记录“前一个节点是谁”递归版则把这个信息隐式地保存在调用栈里。换句话说递归版的 prev 藏在每一层栈帧的 head 参数里返回时一层层带回。这也是为什么递归版的空间复杂度是O(n)——栈的深度就是链表长度。实际生产环境里如果链表非常长递归反转有栈溢出的风险此时首选迭代版。但面试中递归版几乎是必考模板因为它的结构简洁且极具代表性面试官可以从这个题引出你对递归、栈、指针操作的全方位理解。2.4 复杂度分析递归版时间复杂度O(n)每个节点只处理一次空间复杂度O(n)递归栈深度等于链表长度。迭代版时间O(n)空间O(1)。看起来迭代版全面占优但递归版的“学会”价值更大能独立写出这段递归代码说明你已经理解递归回溯的基本模式。我建议读者两个版本都写一遍写完后用3个节点的链表在纸上画出完整的调用栈展开和回溯过程比抄十遍代码都管用。3. 第4题两两交换链表中的节点——成对处理的递归边界3.1 问题的“子问题”到底是什么题目要求给定链表 1-2-3-4返回 2-1-4-3。这里要求是两两交换相邻节点不能只改节点的值必须实实在在地交换节点。如果节点是奇数个最后一个节点保持不动。这个题的递归思路有一个很关键的心智转换第一对节点交换完之后剩下的仍然是一个链表而且这个链表同样需要进行“两两交换”。换句话说swapPairs(head) 的子问题是 swapPairs(head.next.next)。为什么是 head.next.next因为 head 和 head.next 是第一对我们把这一对摘出来处理从第三个节点开始的剩余部分才是一个完整的新子问题。这个子问题的设定比反转链表稍微绕一点。反转链表里子问题是 head.next 开始的整条链表而两两交换里子问题是 head.next.next 开始的链表因为第一对节点被“优先处理”了。这种差别会导致代码结构明显不同需要仔细体会。3.2 递归代码与执行过程拆解def swapPairs(head): if head is None or head.next is None: return head nxt head.next head.next swapPairs(nxt.next) nxt.next head return nxt还是用4节点链表 1-2-3-4 来模拟。调用 swapPairs(1)终止条件不满足nxt 是节点2。然后递归调用 swapPairs(3)这一层要先处理 3-4 这对。swapPairs(3) 里nxt 是节点4递归调用 swapPairs(None)返回 None。于是 head.next节点3的下一个指向 Nonenxt.next head也就是节点4指向节点3返回节点4。此时 3-4 已经被翻成了 4-3。回到 swapPairs(1) 这一层head.next swapPairs(3) 的结果也就是节点4。注意此时节点4后面跟着的是33的next是None。然后 nxt.next head即节点2指向节点1返回节点2。最终链表变成 2-1-4-3完美。这里的执行顺序非常有讲究必须先递归处理后面的子链表再处理当前这一对的指针交接。如果顺序颠倒先执行 nxt.next head再递归处理后面的你会发现子链表的头节点已经找不到了因为 nxt 的指针已经被改过。我在带新手的时候发现这是一道特别好用的“陷阱题”——能看出来这里顺序有讲究的人基本上已经掌握了递归回溯的节奏。3.3 边界条件与常见踩坑边界条件依然只有一个head 为空或者 head.next 为空。前者对应空链表后者对应只剩一个节点这两种情况都不需要再交换。奇数长度链表走到最后一层时就会触发 head.next is None 这个条件最后一个节点原样返回非常自然。常见的踩坑点在代码上没有太大变化但理解上容易出偏。第一个是把子问题想成 swapPairs(head.next)这会把整个链表错乱交换逻辑完全失效。第二个是忘记保存 nxt直接操作 head.next.next 之后回不来了。第三个是返回值写错。这个题的返回值是第二节点原链表中的第二个节点因为交换之后它才是新链表的头。很多人习惯性返回 head结果一整个链表最后只剩两个节点。3.4 与反转链表的区别整体反转 vs 成对反转把这两道题放一起对比非常有意思。反转链表是“全局”地逆序所有节点的指针方向整体翻转两两交换是“局部”地成对翻转每两个节点一个小团体团体的内部方向翻转但团体之间的顺序保持原样。体现在递归上反转链表不需要处理“分组边界”直接对 head.next 开头的整条子链表反转两两交换则必须先跨过一对节点对第三个节点开头的子链表递归。如果你能把这两道题的分界点讲出来递归的“子问题”视角基本就立住了。还有一个隐藏考点两两交换的迭代版其实更考验指针操作需要同时维护 prev、cur、nxt 三个位置的连接关系。我通常建议先写递归版再写迭代版因为递归版把“子问题”的边界画得很清楚迭代版则把“指针交接”的细节暴露无遗。两个版本都写出来这个题才算吃透。4. 第5题快速幂——递归从链表延伸到数值计算4.1 从朴素循环到二分的本质第三、四题都在链表上做文章第五题突然跳到数值计算很多人会觉得突兀。但快速幂这个题恰恰是检验“递归思想是否真的学到手”的分水岭因为它的子问题拆分不再依赖任何数据结构纯粹是一个数学恒等式。先看朴素解法计算 x 的 n 次幂直接用一个循环累乘 n 次。这个做法的复杂度是O(n)n 一旦变成10的9次方量级程序直接超时。快速幂的核心观察到一句话x^n 可以拆成 x^(n/2) 的平方即 (x^(n/2))^2。如果 n 是偶数这个等式是精确的如果 n 是奇数稍微调整一下x^n (x^(n/2))^2 * x。这样算下去每一轮指数减半总轮数就是O(logn)。这个拆分的思想本质上就是“二分”。二分的威力在于n 从10的9次方降到0只需要大约30步。这就是为什么快速幂能扛住超大指数的原因。4.2 递归版快速幂奇偶分支的写法def myPow(x, n): if n 0: return 1 if n 0: return 1.0 / myPow(x, -n) half myPow(x, n // 2) if n % 2 0: return half * half else: return half * half * x先回答三问。终止条件n 为0时任何非零数的0次幂都是1。这是数学上最干净利落的边界。子问题拆分计算 x 的 n//2 次幂把指数砍半。回溯处理根据 n 的奇偶性把子问题的结果平方或者平方后再多乘一个 x。这里有一点要提醒递归里先算 half再根据 n 的奇偶决定怎么用 half这个顺序千万不能反。如果写成 if n % 2 0: return myPow(x, n//2) * myPow(x, n//2)那每一次都会递归调用两次整个算法退化成O(n)白费了二分的心血。先算一次 half再平方复用这才是快速幂的精髓。用 myPow(2, 10) 实际推演一遍n10偶数计算 myPow(2,5)myPow(2,5) 需要 myPow(2,2)myPow(2,2) 需要 myPow(2,1)myPow(2,1) 需要 myPow(2,0) 返回1然后因为1是奇数返回1122回到 n2 偶数返回224回到 n5 奇数返回44232回到 n10 偶数返回32321024。最终结果正确而且整个调用链的层级只有4层。对比一下用循环直接乘10次工作量大得多。4.3 负数指数与整数溢出处理上面代码里 n 0 的分支处理了负指数先把问题变成计算 x 的正指数次幂最后取倒数。数学上就是 x^(-n) 1 / x^n。这个思路本身不复杂但藏着一个特别经典的坑在C和Java里int 的最小值 Integer.MIN_VALUE 的绝对值比 int 的最大值大1。如果你直接写 -n在 n -2147483648 时-n 还是 -2147483648因为整数溢出了。这样递归就永远结束不了无限循环下去。解决方式有两种。在 Java 中把参数类型改成 long或者对 n 先做一个特殊处理。用 Python 写就没有这个烦恼Python 的整数不限制在32位内。但我讲这个坑的意义在于递归题写多了很多人会把注意力全放在递归逻辑上忽略了语言层面的边界问题。面试中如果被问到“这个代码有没有 bug”数值溢出往往是第一个要检查的点。另外负数指数的处理还有一个细节当 x 为0且 n 为负数时1/x 会抛除零异常。工程上需要先判断 x 是否接近0。这是从“算法题”到“真实系统”之间的一道坎面试中偶尔会被追问。4.4 迭代版与二进制视角快速幂除了递归版还有迭代版。迭代版从二进制的角度理解更直接把指数 n 写成二进制比如 n 13对应二进制 1101。那么 x^13 x^8 * x^4 * x^1。从最低位开始看 n 的每一位如果这一位是1就把当前累积的 x 幂次乘到结果里每处理完一位x 自身平方一次相当于指数左移一位。def myPow(x, n): if n 0: x 1 / x n -n res 1 while n 0: if n % 2 1: res * x x * x n // 2 return res这个写法空间复杂度是O(1)而且不需要显式维护递归栈。我个人的建议是递归版用于理解数学本质迭代版用于实际写代码。两者时间都是O(logn)但迭代版在实际运行中不会遇到深度过大导致栈溢出的问题。面试时先写递归版然后主动说“这个还可以改成迭代版去掉递归栈”是一个很加分的展示。4.5 取模快速幂与真实场景快速幂的应用不止于算浮点数的幂。在组合数学、密码学、哈希计算中最常见的公式是 (a^b) mod p其中 b 可能大到10的18次方p 是某个大质数。直接算 a^b 会溢出且超时但用快速幂每一步取模结果和性能都能保证。def pow_mod(a, b, p): res 1 a % p while b 0: if b % 2 1: res res * a % p a a * a % p b // 2 return res这个模板我在实际项目里用到过很多次比如生成大整数校验码、实现类 RSA 的加密逻辑时都需要在有限域内快速计算幂。它的核心和快速幂完全一致指数二分奇数位贡献结果幂次自身平方全程取模控制数值范围。如果你已经能独立写出这个模板说明你已经不只是“看懂”快速幂而是能举一反三了。5. 三道题放在一起递归的统一框架5.1 三道题用同一套递归心智模型反转链表、两两交换、快速幂表面上一个是链表局部结构变化一个是链表成对结构变化一个是数值指数减半。但它们都完美适配同一套递归框架先写终止条件再拆分同构子问题最后根据子问题结果做回溯合并。我整理了一个对照表读者可以保存下来反复看题目终止条件子问题拆分回溯处理反转链表head 为空或 head.next 为空反转 head.next 开头的子链表head.next.next head; head.next None两两交换链接节点head 为空或 head.next 为空对 head.next.next 开头的子链表做 swapPairs先让 head.next 指向子问题结果再让 nxt.next 指向 head快速幂n 0计算 x 的 n//2 次幂偶数直接平方奇数平方后再乘 x注意看第二列三个终止条件本质上是同一个逻辑问题规模已经小到不需要再做任何操作。反转链表里只有一个节点或没有节点两两交换里只剩一个节点或没有节点快速幂里指数为0。第三列则是“怎么把问题变小”链表类问题是靠 next 指针剥节点数值类问题是靠除以2砍指数。第四列是每一题独特的“组装”逻辑也是面试官最想听你讲清楚的部分。5.2 遇到递归题先问三个问题基于这三道题我总结出一个通用的递归解题流程。拿到任何一道新题先不要急着写代码先对着纸面问自己三个问题。第一问什么情况下不需要递归这个问题的答案通常就是终止条件。空链表、单节点、指数为0、数组长度为1、搜索区间为空这些都是最常见的“不需要再递归”的场景。找到这个边界代码的第一段就写好了。第二问怎么把当前问题变成一个更小的同类问题这个问题的答案决定了递归的方向和参数变化。链表题通常是 head.next 或者 head.next.next数组题通常是中间切开取一半数值题通常是指数减半。这一步的关键是“同构”——子问题必须长得和原问题一模一样只是规模更小。第三问拿到子问题的结果之后我要用它做什么这一步要非常具体地写出来。反转链表是把子链表结果的头节点接到当前节点前面两两交换是让当前节点的 next 指向子问题结果再让第二节点指向当前节点快速幂是让子问题的结果自乘奇数还要补乘一个 x。想清楚这一步递归函数的 return 语句就不会写错。5.3 调试递归的实用技巧递归代码写对了画起来却很费劲。我自己的习惯是“打印缩进法”。在递归函数入口打印当前参数出口打印返回值通过缩进符展示调用深度一下子就能看清整个递归的递和归。def reverseList(head, depth0): print( * depth freverseList({head.val if head else None})) if head is None or head.next is None: print( * depth freturn {head.val if head else None}) return head new_head reverseList(head.next, depth 1) print( * depth fafter sub: new_head{new_head.val}, set {head.next.val}.next{head.val}) head.next.next head head.next None print( * depth freturn {new_head.val}) return new_head输出里你会清楚地看到先是一层层往下的 depth 增加对应“递”然后是一层层往上的 depth 减少对应“归”。这是我调试递归最常用也是最好用的方法建议大家都试试。看完一次打印输出之后很多在脑子里绕不清的指针关系直接变成了一张张清晰的时序图。6. 常见问题排查与避坑实录前面每道题都提到了一些易错点这里我把实操中最常见的五类问题集中梳理一下每一条都是真实踩过的坑。第一类终止条件遗漏导致递归不停止。最典型的是反转链表只判断 head is None漏了 head.next is None。单节点链表往下调用时head.next 为 None再进入下一层就会访问 None.next 抛异常。排查技巧是打印输入参数观察 depth 是否一直在增加。解决方法是写递归函数的第一件事永远是问自己这个问题的输入最小能有多小空单元素双元素第二类空指针异常。发生在链表的 next 指针还没有判断就进行访问的情况下比如两两交换里没有先确认 head.next 是否存在就取 head.next.next。这类问题一般出现在终止条件写得太宽松的代码里。排查技巧是检查所有 .next 操作之前是否已经确认过当前节点非空。第三类链表形成环导致死循环。反转链表里漏写 head.next None 是罪魁祸首两两交换里顺序写反也可能产生环。判断方法打印链表前几个节点如果出现重复节点说明有环。解决问题的方法是扣住一个原则改完指针之后被绕过的旧指针必须置 None。第四类递归深度过大栈溢出。链表特别长的时候递归版反转链表和两两交换都可能爆栈。此时要么改成迭代版要么在工程中直接规避递归。面试时建议主动说明这种trade-off会让面试官觉得你有工程经验。快速幂的递归深度只有O(logn)一般不用担心。第五类数值溢出与除零。快速幂在 C 和 Java 里要特别注意 Integer.MIN_VALUE 取负溢出的问题同时也得处理 x 为0且指数为负数的除零场景。这一类 bug 的隐蔽性在于单测用常规数值时完全正常只有边界值触发。症状可能原因排查方法解决思路程序栈溢出终止条件缺失或递归深度太大打印调用深度补终止条件或改迭代空指针异常未判断 next 就访问 next.next检查所有 .next 前的判空收紧终止条件遍历链表死循环旧指针未置 None链表成环打印遍历结果观察重复节点反转后 head.next None结果少节点/多节点返回值写错返回了 head 而不是新头打印每层返回值确认新头是子问题结果的头部结果错误但逻辑看似正常递归调用顺序颠倒用打印缩进法看执行顺序先递归处理子问题再回溯合并最后再分享一个我自己的练习习惯。这三道题我都要求自己在白纸上手写一遍不靠编辑器提示。写完递归版之后再写一遍迭代版然后对比两个版本的指针变化过程。这个过程看起来笨但效率极高。如果你现在正卡在递归上别去看更多讲解视频停下来把这三个题按照上面的对照表手推三遍再把代码敲三遍基本上递归这道坎就迈过去了。后续再往深走你可以试试 K 个一组翻转链表、矩阵快速幂、线段树这类更进阶的题目你会发现它们骨子里用的还是今天这一套“递归三问”的方法。