先说个结论递归在算法面试里的地位有点像做菜时的“火候”——你问每个人都会真到关键时候能不能收放自如才是拉开差距的地方。反转链表、两两交换链表中的节点、快速幂这三道题我经常放在一起讲因为它们刚好覆盖了递归的三种典型结构线性递归、成对递归、倍增递归。只要把这三道题真正吃透后面你再去碰搜索、回溯、树形DP这些内容会发现大家都在说“递归”但你脑子里的模型和别人的完全不在一个层面。这篇文章适合两类人看一类是正在备战算法面试、刷题刷到“递归”就想跳过的同学另一类是学校刚教到数据结构、想彻底搞懂递归到底是怎么“自己调用自己”的自学者。我会用最直白的方式把递归怎么想、代码怎么一步步搭出来、边界条件为什么那么写全部讲透。不整虚的直接进入正题。1. 递归思维的第一步别再被“自己调用自己”绕晕很多人学递归卡在第一步就动不了函数里面调用自己那它到底怎么结束这不就是死循环吗其实这个理解方向从一开始就偏了。递归不是“自己调用自己”这个形式而是“把一个大规模问题拆成一个更小规模的同类问题 一个本层需要处理的动作”。1.1 把地基打牢“递”与“归”其实是两段完全不同的逻辑递归这个中文翻译特别误导人。英文叫 recursion核心就一个“re-”表示重复。很多人以为递归是“一路往深了走”但真正重要的是它的“归”的阶段——调用栈一层层退回来每一层都在做自己的那个“小动作”。我用一个特别生活化的例子你在排队买奶茶队伍很长你想知道自己是第几个。你不可能从头数于是你问前面的人“你是第几个”前面的人也不知道于是他又问前面的人……一直问到队首队首说“我是第1个”。然后这个答案往后传第2个人知道自己排第2第3个人知道排第3传到你这儿你就知道了第n个。这个例子里的“往前问”叫递“往回传答案”叫归。重点在于每个人只需要做两件事——往前问出一个答案然后对答案做一次“加一”再传回去。你不用真的从头数到尾你只需要信任前面那个人能给出正确的答案。这个“信任”就是递归里最重要也最反直觉的心法。1.2 递归三要素终止条件、本层任务、信任子调用我在带新人写递归题的时候不管题目是什么都要求先默念三句话我现在写的是“f(head)表示什么”——函数定义要极其清晰什么情况下这个问题小到不用拆了——终止条件我假设f(head.next)已经帮我算好了——递推关系。比如说反转链表函数定义就是“f(head)返回从head开始反转后的新头”。终止条件有两种链表为空或者只有一个节点这时链表已经反转好了直接返回。递推关系就是先把head.next之后的链表反转好拿到新头然后让head.next这个节点的next指向head把head变成最后一个节点。注意第3点“假设子调用已经算好了”这听着像作弊但其实是递归能成立的核心。你的任务不是去操心后面整条链表怎么反转你只需要操心当后面的链表已经被反转好之后我这个head怎么接上去。这样一想递归立刻好写很多。1.3 递归为什么会让很多工程师犹豫调用栈与空间代价学递归你必须知道一个事实每一层递归都会占用一份栈空间存当前函数的局部变量和返回地址。在刷题时这意味着递归版本的时间复杂度可能和迭代一样但空间复杂度几乎总是O(n)n是递归深度。Python默认递归深度大概在1000层左右超过就会抛RecursionError。这个限制在链表题里特别容易踩如果面试官给了一个长度上万甚至十万的链表你的递归版反转链表会直接爆栈。这不是你代码写错了而是工具的物理限制。所以后面我会反复强调递归版本适合理解思路但真要处理超大数据量得会手动改成迭代。2. 反转链表最典型的线性递归长什么样反转链表这道题题目本身很简单给一个1→2→3→4→5的单链表输出5→4→3→2→1。你如果用迭代写几步循环就出来了。但我见过不少同学在面试里被要求“能不能用递归写一下”然后当场愣住。原因在于迭代版本是顺着链表往前走递归版本是倒着往回走思维方向完全相反。2.1 先看一眼迭代版本三指针翻转的直觉迭代反转的经典写法是这样的def reverseList(head): prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev核心就是三个指针prev、curr、nxt每轮循环把curr.next指向前一个节点prev然后整体往右移。这个版本最需要注意的是如果你在改curr.next之前没有先保存nxt链表就断了后面全丢。这个坑面试里特别常见我见过不下十个同学在这里卡住。迭代版本的优势是空间O(1)缺点是你得同时维护三个指针脑子里一定要有一张链表变化的动态图。很多人写错不是因为逻辑不对而是指针一多手就跟不上脑子。2.2 递归版核心代码拆解代码只有四行关键看你怎么解释递归版本反而短一些def reverseList(head): if not head or not head.next: return head newHead reverseList(head.next) head.next.next head head.next None return newHead我来一行一行拆。很多人看不懂卡在这两行head.next.next head 和 head.next None。假设链表是1→2→3→4→5调用reverseList(1)的时候函数里先不管别的直接递归调用reverseList(2)。请记住此刻的意义我们信任reverseList(2)能把2→3→4→5反转成5→4→3→2并且返回新头5。递归回来之后变量newHead的值就是节点5。接下来当前这个节点是1它的next仍然是2。既然2已经是反转后链表的最后一个节点了我们要做的是让2的next指向1也就是head.next.next head。这句代码的意思是把“当前节点的下一个节点”的下一个指向当前节点。理解这句话是吃透这个递归版的关键。然后head.next None。为什么必须置空因为原来的head可能还指着2如果不把head.next断掉新链表里就会出现循环1-22-1这就成环了。置空之后1成为反转后链表的尾节点完美收尾。整个递归过程中newHead这个变量从头到尾都是节点5每一层都只是把它往上返。每一层实际做的事情只是把当前节点挪到已反转链表的尾部。我让很多同学在纸上画这个调用栈画完基本都能懂。如果你手边有纸笔建议你画一个3个节点的链表把每一层递归的入参、出参、指针变化列出来比看十遍文章都有用。2.3 边界条件与面试追问别在空链表和单节点上翻车终止条件里那句not head or not head.next顺序一定不能反。如果链表是空的head本身是None你还去访问head.next就直接报错了。先判断not head再判断not head.next这是防御性编程的一部分。单节点链表也走这个分支。只有一个节点时它反转之后还是它自己直接返回。这个边界处理好了很多奇奇怪怪的报错都能消掉。面试官经常顺着这个递归版继续追问你这个递归深度是多少如果链表特别长会不会栈溢出你空间复杂度多少能不能改成迭代所以我的建议是这道题的递归版和迭代版都要背熟最好还能说出为什么各有优劣。递归版代码短、不易出错但空间O(n)迭代版空间O(1)但三个指针容易写乱。面试时先说你更熟悉哪个再说另一个版本怎么实现基本就能把这题吃透。3. 两两交换链表中的节点成对递归的分寸感这道题是LeetCode第24题题目描述给定一个链表两两交换其中相邻节点并返回交换后的链表。比如1→2→3→4交换后变成2→1→4→3。如果不能修改节点值你只能真正去改变节点之间的指针关系。这道题比反转链表难一档因为递归的“本层任务”变成了一个成对操作。3.1 先给函数一个清晰定义swapPairs(head)到底负责什么写递归第一步永远是定义清楚函数。def swapPairs(head): if not head or not head.next: return head second head.next rest swapPairs(second.next) second.next head head.next rest return secondswapPairs(head)的定义是从head开始把相邻节点两两交换返回新的头节点。这点必须想清楚。因为head是原来的第一个节点交换之后它不再是头了新的头是head.next也就是代码里的second。这个定义定了后面的逻辑就顺了。递归调用写的是swapPairs(second.next)注意不是swapPairs(head.next)因为head.next就是second我们要处理的是“第二个节点之后的部分”。也就是说把后面的链表看成一条独立的子链表递归去交换它拿到一个“已经处理好的新头”记为rest。3.2 中间的指针重连为什么要按这个顺序先处理后面再交换前面我用1→2→3→4举例把整个流程走一遍。先说递归调用swapPairs(1)因为1和2都在second 2。然后rest swapPairs(3)。注意此刻问题缩成了“3→4”与原问题完全同构。swapPairs(3)里second 4rest swapPairs(None)返回None。然后把4.next指向33.next指向None返回4。所以swapPairs(3)完成之后链表变成4→3rest拿到的是4。回到swapPairs(1)现在手里有head1second2rest4。我们需要把2指向1再把1指向rest。所以执行second.next head得到2→1再执行head.next rest得到1→4。此刻整个链表是2→1→4→3完美。这个顺序不能乱。如果你先执行head.next rest那head原来的next信息没了second还指不指得到2就说不清了。你先改head.next再把second.nexthead指针指向会乱成一锅粥。先保存好second再先连后面、后连前面这个顺序是这道题最容易写错的地方。还有一个细节为什么递归调用要放在交换之前因为你先递归把后面处理好拿到rest之后再回头处理前两个节点这样前两个节点中的head.next才有地方接。如果先交换前两个节点再递归处理后面你会发现head的next已经被改成second了后面的子链表就找不到了。所以必须先递归后处理当前层。这种“先走到底再自底向上组装”的模式和反转链表是完全一致的。3.3 和反转链表的对比同样是链表递归模式差异在哪反转链表和两两交换这两道题很多同学搞混。我用一个角度帮你区分反转链表是“所有节点都参与重连”它的本层任务是把当前节点接到已反转子链表的末尾两两交换是“每两个节点一组参与重连”它的本层任务是处理当前这一对然后接上后面已经处理好的子链表。前者的递归返回值是“整个子链表的新头”这个新头不会变后者的递归返回值也是“整个子链表的新头”但每层都会变成second——新的头节点不同了。所以两两交换的return second这一步是最容易漏的。如果写代码时还返回head那结果就是链从中间断了或者局部交换了但整体没接上。如果你做这道题画递归树你会发现它比反转链表多了“成对”的概念。反转链表每一层只有一个节点在“动”两两交换每一层有两个节点在“动”。所以两者都是线性递归但因为操作的单位不同代码结构也有了明显差异。把这两道题放一起比较着练你对递归的敏感度会一下子提上来。4. 快速幂递归的“倍增”思维复杂度直降快速幂是一个数学色彩比较重的题题目也很短实现pow(x, n)计算x的n次幂。很多人第一反应是写个循环乘n次时间复杂度O(n)。但面试官想要的显然不是这个而是O(logn)的版本。快速幂就是用递归做“指数折半”这正是递归的倍增模式。4.1 数学直觉x的n次方真的需要乘n次吗核心公式很简单如果n是偶数x^n (x^(n/2))^2如果n是奇数x^n (x^(n/2))^2 * x。这个公式反过来看更直观x^10 (x^5)^2而x^5 (x^2)^2 * x。你看每一次n都能直接缩小一半。所以原本需要10次乘法现在只需要几次。用字母表示T(n) T(n/2) O(1)套主定理或者直接看就是O(logn)。拿二进制来理解更彻底。n可以写成二进制比如10就是1010也就是82。所以x^10 x^8 * x^2。快速幂本质上是把一个指数拆成二进制从低位到高位逐位处理每一位“乘一次底数”然后底数不停自乘对应二进制位权值不断翻倍。这个过程和递归的“折半”是同一件事。4.2 递归实现奇偶分支边界怎么处理def myPow(x, n): if n 0: return 1.0 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这个版本已经能过绝大多数测试用例但我建议你理解每一步。n0返回1是终止条件。n0的时候x的负整数次幂等于1除以x的正数次幂所以先递归算x^(-n)再取倒数。然后是关键的奇偶分支先递归求出half myPow(x, n//2)。为什么先递归因为无论n是奇数还是偶数我们都需要先知道x^(n//2)的值然后看n的奇偶决定再乘一次x还是直接平方。这个写法比直接写两个递归分支一个算x^(n-1)再乘x更高效因为n//2之后子问题直接变成一半而不是仅仅减一。还有一个小坑在Python里n//2和n%2配合使用在n为正数时完全没问题。但如果n是负数我们已经在前面做了取反处理所以进入主体的时候n一定非负可以放心用//和%。4.3 面试追问的三种变形取模、递推、迭代面试官一般不会让你写完递归就放你走他必然追加问题。第一个追问是取模。题目变成“计算x^n mod m”这时候我们不能在最后取一次模因为中间过程会爆。正确做法是每一步乘法都取模half myPow(x, n//2, m)然后result (half * half) % m奇数再加乘x后取模。你只需要把代码里的return都包裹一个% m复杂度不变。第二个追问是能不能用迭代。递归版的空间是O(logn)的因为调用栈深度就是指数二进制的位数。迭代版可以做到空间O(1)用上面提到的二进制展开思路。核心逻辑不断看n的最低位如果是1就累乘当前base然后base自乘一次n右移一位。这样一轮循环就处理一个二进制位最多循环logn次。def myPow(x, n): if n 0: x 1 / x n -n result 1.0 base x while n 0: if n % 2 1: result * base base * base n // 2 return result这个迭代版我再讲一个容易错的地方base每次循环都要自乘即使n当前位是0也要自乘。因为位权值是翻倍的下一次可能需要用到。比如x^8的4次方你要经历basex^2、x^4、x^8的过程每一位都得累乘上去。第三个追问是把问题延伸到矩阵快速幂比如斐波那契数列用矩阵的形式求第n项。思路和标量快速幂完全一样只是把底数从实数变成矩阵把乘法变成矩阵乘法。如果你理解了标量快速幂矩阵版本就是套壳。5. 实战经验题型识别、避坑清单与练习方法三道题讲完了最后这部分是纯经验分享。我带过不少同学也做过不少面试官。我知道递归写不出来的时候那种挫败感——明明代码就几行但脑子里就是转不过弯。这里我把自己总结的东西全拿出来。5.1 什么样的题适合递归四个信号你拿到一道题可以先快速判断它适不适合递归。第一问题可以分解成更小规模的同类问题。比如链表题、树题、分治题天然适合递归。第二有明确的终止条件小到一定程度答案显而易见。第三本层的结果能通过子问题的结果组合出来。第四你不需要关心“一共会调用多少次”——这是递归的一个重要特征你只关心“本层做什么”。反过来如果一个问题要求实时交互、状态特别多、或者数据规模大到递归深度不可控那就优先考虑迭代。比如处理超长链表、需要频繁撤销的操作就别硬递归了。5.2 递归三板斧代码套路的固定顺序我总结一个固定的写题顺序每次写递归题都按这个来。第一步先写函数签名把函数的输入输出定义清楚。一定要让人一眼看出返回值代表什么。第二步写终止条件。这是最容易漏的也是边界最容易错的比如链表为空、树节点为空、n等于0等等。第三步写递归调用把子问题交给递归。最后写本层处理逻辑并返回结果。这个顺序千万别跳。很多同学上来就写本层逻辑结果写了一堆发现递归的返回值根本没用上。先定义、再终止、再调用、再处理这句话我希望你能记住。5.3 考官最爱追问的边界与复杂度问题面试官问递归题一般会从三个角度追加。第一复杂度分析。时间复杂度和空间复杂度是多少递归深度和输入规模什么关系。反转链表是O(n)时间和O(n)空间两两交换也是O(n)时间和O(n)空间快速幂是O(logn)时间和O(logn)空间。说复杂度的同时最好主动说出“如果链表特别长递归有爆栈风险可以改成迭代”。第二边界输入。空链表、只有一个节点的链表、n为负数、n为0、x的绝对值特别大这些都要能答得上来。你写的时候就要把边界条件写在最前面这是一种很自然的防御性编程习惯。第三能不能优化。快速幂的递归版其实没有重复子问题每一层只算一次half所以不需要记忆化。有些同学会把快速幂和递归记忆化搞混其实这里并不需要复杂度已经最优了。但如果是斐波那契数列那种重复子问题很多的递归就必须加一个缓存字典否则直接递归会卡死。我在实际训练中最常用的一套方法每道递归题先不写代码先用一个3到4个节点的例子手动画调用栈把每一步入参和返回值标出来确认思路没跑偏再动手。那种代码写了又删、删了又写的痛苦一半以上是因为脑子里没有递归树。额外分享一个避开大坑的小习惯最后多说一句。我自己在带别人做题时发现很多人的递归写错不是逻辑问题而是没有把“函数定义”清清楚楚说出口。反转链表这道题如果你能在心里准确说出“f(head)返回从head开始反转后的新头”后面所有代码就只是服务于这句话一旦你只是模模糊糊觉得“反转一下”写出来的代码大概率是错的。写递归题之前先自言自语把函数定义说一遍这句话值很多遍刷题。这个习惯对我自己帮助很大。每一道递归题我都要求自己在代码开头写一行注释直接注释出返回值是什么。有了这行注释终止条件怎么写、递归调用的返回值怎么用全都顺了。希望这篇拆解对你有用。三道题刷明白“递归”这两个字对你来说就不再是玄学而是一套可复用的思维工具。 
长河君 · 2026/10/14 4:16:56 · 阅读 1.2k 递归算法面试核心：反转链表、两两交换与快速幂全拆解
先说个结论递归在算法面试里的地位有点像做菜时的“火候”——你问每个人都会真到关键时候能不能收放自如才是拉开差距的地方。反转链表、两两交换链表中的节点、快速幂这三道题我经常放在一起讲因为它们刚好覆盖了递归的三种典型结构线性递归、成对递归、倍增递归。只要把这三道题真正吃透后面你再去碰搜索、回溯、树形DP这些内容会发现大家都在说“递归”但你脑子里的模型和别人的完全不在一个层面。这篇文章适合两类人看一类是正在备战算法面试、刷题刷到“递归”就想跳过的同学另一类是学校刚教到数据结构、想彻底搞懂递归到底是怎么“自己调用自己”的自学者。我会用最直白的方式把递归怎么想、代码怎么一步步搭出来、边界条件为什么那么写全部讲透。不整虚的直接进入正题。1. 递归思维的第一步别再被“自己调用自己”绕晕很多人学递归卡在第一步就动不了函数里面调用自己那它到底怎么结束这不就是死循环吗其实这个理解方向从一开始就偏了。递归不是“自己调用自己”这个形式而是“把一个大规模问题拆成一个更小规模的同类问题 一个本层需要处理的动作”。1.1 把地基打牢“递”与“归”其实是两段完全不同的逻辑递归这个中文翻译特别误导人。英文叫 recursion核心就一个“re-”表示重复。很多人以为递归是“一路往深了走”但真正重要的是它的“归”的阶段——调用栈一层层退回来每一层都在做自己的那个“小动作”。我用一个特别生活化的例子你在排队买奶茶队伍很长你想知道自己是第几个。你不可能从头数于是你问前面的人“你是第几个”前面的人也不知道于是他又问前面的人……一直问到队首队首说“我是第1个”。然后这个答案往后传第2个人知道自己排第2第3个人知道排第3传到你这儿你就知道了第n个。这个例子里的“往前问”叫递“往回传答案”叫归。重点在于每个人只需要做两件事——往前问出一个答案然后对答案做一次“加一”再传回去。你不用真的从头数到尾你只需要信任前面那个人能给出正确的答案。这个“信任”就是递归里最重要也最反直觉的心法。1.2 递归三要素终止条件、本层任务、信任子调用我在带新人写递归题的时候不管题目是什么都要求先默念三句话我现在写的是“f(head)表示什么”——函数定义要极其清晰什么情况下这个问题小到不用拆了——终止条件我假设f(head.next)已经帮我算好了——递推关系。比如说反转链表函数定义就是“f(head)返回从head开始反转后的新头”。终止条件有两种链表为空或者只有一个节点这时链表已经反转好了直接返回。递推关系就是先把head.next之后的链表反转好拿到新头然后让head.next这个节点的next指向head把head变成最后一个节点。注意第3点“假设子调用已经算好了”这听着像作弊但其实是递归能成立的核心。你的任务不是去操心后面整条链表怎么反转你只需要操心当后面的链表已经被反转好之后我这个head怎么接上去。这样一想递归立刻好写很多。1.3 递归为什么会让很多工程师犹豫调用栈与空间代价学递归你必须知道一个事实每一层递归都会占用一份栈空间存当前函数的局部变量和返回地址。在刷题时这意味着递归版本的时间复杂度可能和迭代一样但空间复杂度几乎总是O(n)n是递归深度。Python默认递归深度大概在1000层左右超过就会抛RecursionError。这个限制在链表题里特别容易踩如果面试官给了一个长度上万甚至十万的链表你的递归版反转链表会直接爆栈。这不是你代码写错了而是工具的物理限制。所以后面我会反复强调递归版本适合理解思路但真要处理超大数据量得会手动改成迭代。2. 反转链表最典型的线性递归长什么样反转链表这道题题目本身很简单给一个1→2→3→4→5的单链表输出5→4→3→2→1。你如果用迭代写几步循环就出来了。但我见过不少同学在面试里被要求“能不能用递归写一下”然后当场愣住。原因在于迭代版本是顺着链表往前走递归版本是倒着往回走思维方向完全相反。2.1 先看一眼迭代版本三指针翻转的直觉迭代反转的经典写法是这样的def reverseList(head): prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev核心就是三个指针prev、curr、nxt每轮循环把curr.next指向前一个节点prev然后整体往右移。这个版本最需要注意的是如果你在改curr.next之前没有先保存nxt链表就断了后面全丢。这个坑面试里特别常见我见过不下十个同学在这里卡住。迭代版本的优势是空间O(1)缺点是你得同时维护三个指针脑子里一定要有一张链表变化的动态图。很多人写错不是因为逻辑不对而是指针一多手就跟不上脑子。2.2 递归版核心代码拆解代码只有四行关键看你怎么解释递归版本反而短一些def reverseList(head): if not head or not head.next: return head newHead reverseList(head.next) head.next.next head head.next None return newHead我来一行一行拆。很多人看不懂卡在这两行head.next.next head 和 head.next None。假设链表是1→2→3→4→5调用reverseList(1)的时候函数里先不管别的直接递归调用reverseList(2)。请记住此刻的意义我们信任reverseList(2)能把2→3→4→5反转成5→4→3→2并且返回新头5。递归回来之后变量newHead的值就是节点5。接下来当前这个节点是1它的next仍然是2。既然2已经是反转后链表的最后一个节点了我们要做的是让2的next指向1也就是head.next.next head。这句代码的意思是把“当前节点的下一个节点”的下一个指向当前节点。理解这句话是吃透这个递归版的关键。然后head.next None。为什么必须置空因为原来的head可能还指着2如果不把head.next断掉新链表里就会出现循环1-22-1这就成环了。置空之后1成为反转后链表的尾节点完美收尾。整个递归过程中newHead这个变量从头到尾都是节点5每一层都只是把它往上返。每一层实际做的事情只是把当前节点挪到已反转链表的尾部。我让很多同学在纸上画这个调用栈画完基本都能懂。如果你手边有纸笔建议你画一个3个节点的链表把每一层递归的入参、出参、指针变化列出来比看十遍文章都有用。2.3 边界条件与面试追问别在空链表和单节点上翻车终止条件里那句not head or not head.next顺序一定不能反。如果链表是空的head本身是None你还去访问head.next就直接报错了。先判断not head再判断not head.next这是防御性编程的一部分。单节点链表也走这个分支。只有一个节点时它反转之后还是它自己直接返回。这个边界处理好了很多奇奇怪怪的报错都能消掉。面试官经常顺着这个递归版继续追问你这个递归深度是多少如果链表特别长会不会栈溢出你空间复杂度多少能不能改成迭代所以我的建议是这道题的递归版和迭代版都要背熟最好还能说出为什么各有优劣。递归版代码短、不易出错但空间O(n)迭代版空间O(1)但三个指针容易写乱。面试时先说你更熟悉哪个再说另一个版本怎么实现基本就能把这题吃透。3. 两两交换链表中的节点成对递归的分寸感这道题是LeetCode第24题题目描述给定一个链表两两交换其中相邻节点并返回交换后的链表。比如1→2→3→4交换后变成2→1→4→3。如果不能修改节点值你只能真正去改变节点之间的指针关系。这道题比反转链表难一档因为递归的“本层任务”变成了一个成对操作。3.1 先给函数一个清晰定义swapPairs(head)到底负责什么写递归第一步永远是定义清楚函数。def swapPairs(head): if not head or not head.next: return head second head.next rest swapPairs(second.next) second.next head head.next rest return secondswapPairs(head)的定义是从head开始把相邻节点两两交换返回新的头节点。这点必须想清楚。因为head是原来的第一个节点交换之后它不再是头了新的头是head.next也就是代码里的second。这个定义定了后面的逻辑就顺了。递归调用写的是swapPairs(second.next)注意不是swapPairs(head.next)因为head.next就是second我们要处理的是“第二个节点之后的部分”。也就是说把后面的链表看成一条独立的子链表递归去交换它拿到一个“已经处理好的新头”记为rest。3.2 中间的指针重连为什么要按这个顺序先处理后面再交换前面我用1→2→3→4举例把整个流程走一遍。先说递归调用swapPairs(1)因为1和2都在second 2。然后rest swapPairs(3)。注意此刻问题缩成了“3→4”与原问题完全同构。swapPairs(3)里second 4rest swapPairs(None)返回None。然后把4.next指向33.next指向None返回4。所以swapPairs(3)完成之后链表变成4→3rest拿到的是4。回到swapPairs(1)现在手里有head1second2rest4。我们需要把2指向1再把1指向rest。所以执行second.next head得到2→1再执行head.next rest得到1→4。此刻整个链表是2→1→4→3完美。这个顺序不能乱。如果你先执行head.next rest那head原来的next信息没了second还指不指得到2就说不清了。你先改head.next再把second.nexthead指针指向会乱成一锅粥。先保存好second再先连后面、后连前面这个顺序是这道题最容易写错的地方。还有一个细节为什么递归调用要放在交换之前因为你先递归把后面处理好拿到rest之后再回头处理前两个节点这样前两个节点中的head.next才有地方接。如果先交换前两个节点再递归处理后面你会发现head的next已经被改成second了后面的子链表就找不到了。所以必须先递归后处理当前层。这种“先走到底再自底向上组装”的模式和反转链表是完全一致的。3.3 和反转链表的对比同样是链表递归模式差异在哪反转链表和两两交换这两道题很多同学搞混。我用一个角度帮你区分反转链表是“所有节点都参与重连”它的本层任务是把当前节点接到已反转子链表的末尾两两交换是“每两个节点一组参与重连”它的本层任务是处理当前这一对然后接上后面已经处理好的子链表。前者的递归返回值是“整个子链表的新头”这个新头不会变后者的递归返回值也是“整个子链表的新头”但每层都会变成second——新的头节点不同了。所以两两交换的return second这一步是最容易漏的。如果写代码时还返回head那结果就是链从中间断了或者局部交换了但整体没接上。如果你做这道题画递归树你会发现它比反转链表多了“成对”的概念。反转链表每一层只有一个节点在“动”两两交换每一层有两个节点在“动”。所以两者都是线性递归但因为操作的单位不同代码结构也有了明显差异。把这两道题放一起比较着练你对递归的敏感度会一下子提上来。4. 快速幂递归的“倍增”思维复杂度直降快速幂是一个数学色彩比较重的题题目也很短实现pow(x, n)计算x的n次幂。很多人第一反应是写个循环乘n次时间复杂度O(n)。但面试官想要的显然不是这个而是O(logn)的版本。快速幂就是用递归做“指数折半”这正是递归的倍增模式。4.1 数学直觉x的n次方真的需要乘n次吗核心公式很简单如果n是偶数x^n (x^(n/2))^2如果n是奇数x^n (x^(n/2))^2 * x。这个公式反过来看更直观x^10 (x^5)^2而x^5 (x^2)^2 * x。你看每一次n都能直接缩小一半。所以原本需要10次乘法现在只需要几次。用字母表示T(n) T(n/2) O(1)套主定理或者直接看就是O(logn)。拿二进制来理解更彻底。n可以写成二进制比如10就是1010也就是82。所以x^10 x^8 * x^2。快速幂本质上是把一个指数拆成二进制从低位到高位逐位处理每一位“乘一次底数”然后底数不停自乘对应二进制位权值不断翻倍。这个过程和递归的“折半”是同一件事。4.2 递归实现奇偶分支边界怎么处理def myPow(x, n): if n 0: return 1.0 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这个版本已经能过绝大多数测试用例但我建议你理解每一步。n0返回1是终止条件。n0的时候x的负整数次幂等于1除以x的正数次幂所以先递归算x^(-n)再取倒数。然后是关键的奇偶分支先递归求出half myPow(x, n//2)。为什么先递归因为无论n是奇数还是偶数我们都需要先知道x^(n//2)的值然后看n的奇偶决定再乘一次x还是直接平方。这个写法比直接写两个递归分支一个算x^(n-1)再乘x更高效因为n//2之后子问题直接变成一半而不是仅仅减一。还有一个小坑在Python里n//2和n%2配合使用在n为正数时完全没问题。但如果n是负数我们已经在前面做了取反处理所以进入主体的时候n一定非负可以放心用//和%。4.3 面试追问的三种变形取模、递推、迭代面试官一般不会让你写完递归就放你走他必然追加问题。第一个追问是取模。题目变成“计算x^n mod m”这时候我们不能在最后取一次模因为中间过程会爆。正确做法是每一步乘法都取模half myPow(x, n//2, m)然后result (half * half) % m奇数再加乘x后取模。你只需要把代码里的return都包裹一个% m复杂度不变。第二个追问是能不能用迭代。递归版的空间是O(logn)的因为调用栈深度就是指数二进制的位数。迭代版可以做到空间O(1)用上面提到的二进制展开思路。核心逻辑不断看n的最低位如果是1就累乘当前base然后base自乘一次n右移一位。这样一轮循环就处理一个二进制位最多循环logn次。def myPow(x, n): if n 0: x 1 / x n -n result 1.0 base x while n 0: if n % 2 1: result * base base * base n // 2 return result这个迭代版我再讲一个容易错的地方base每次循环都要自乘即使n当前位是0也要自乘。因为位权值是翻倍的下一次可能需要用到。比如x^8的4次方你要经历basex^2、x^4、x^8的过程每一位都得累乘上去。第三个追问是把问题延伸到矩阵快速幂比如斐波那契数列用矩阵的形式求第n项。思路和标量快速幂完全一样只是把底数从实数变成矩阵把乘法变成矩阵乘法。如果你理解了标量快速幂矩阵版本就是套壳。5. 实战经验题型识别、避坑清单与练习方法三道题讲完了最后这部分是纯经验分享。我带过不少同学也做过不少面试官。我知道递归写不出来的时候那种挫败感——明明代码就几行但脑子里就是转不过弯。这里我把自己总结的东西全拿出来。5.1 什么样的题适合递归四个信号你拿到一道题可以先快速判断它适不适合递归。第一问题可以分解成更小规模的同类问题。比如链表题、树题、分治题天然适合递归。第二有明确的终止条件小到一定程度答案显而易见。第三本层的结果能通过子问题的结果组合出来。第四你不需要关心“一共会调用多少次”——这是递归的一个重要特征你只关心“本层做什么”。反过来如果一个问题要求实时交互、状态特别多、或者数据规模大到递归深度不可控那就优先考虑迭代。比如处理超长链表、需要频繁撤销的操作就别硬递归了。5.2 递归三板斧代码套路的固定顺序我总结一个固定的写题顺序每次写递归题都按这个来。第一步先写函数签名把函数的输入输出定义清楚。一定要让人一眼看出返回值代表什么。第二步写终止条件。这是最容易漏的也是边界最容易错的比如链表为空、树节点为空、n等于0等等。第三步写递归调用把子问题交给递归。最后写本层处理逻辑并返回结果。这个顺序千万别跳。很多同学上来就写本层逻辑结果写了一堆发现递归的返回值根本没用上。先定义、再终止、再调用、再处理这句话我希望你能记住。5.3 考官最爱追问的边界与复杂度问题面试官问递归题一般会从三个角度追加。第一复杂度分析。时间复杂度和空间复杂度是多少递归深度和输入规模什么关系。反转链表是O(n)时间和O(n)空间两两交换也是O(n)时间和O(n)空间快速幂是O(logn)时间和O(logn)空间。说复杂度的同时最好主动说出“如果链表特别长递归有爆栈风险可以改成迭代”。第二边界输入。空链表、只有一个节点的链表、n为负数、n为0、x的绝对值特别大这些都要能答得上来。你写的时候就要把边界条件写在最前面这是一种很自然的防御性编程习惯。第三能不能优化。快速幂的递归版其实没有重复子问题每一层只算一次half所以不需要记忆化。有些同学会把快速幂和递归记忆化搞混其实这里并不需要复杂度已经最优了。但如果是斐波那契数列那种重复子问题很多的递归就必须加一个缓存字典否则直接递归会卡死。我在实际训练中最常用的一套方法每道递归题先不写代码先用一个3到4个节点的例子手动画调用栈把每一步入参和返回值标出来确认思路没跑偏再动手。那种代码写了又删、删了又写的痛苦一半以上是因为脑子里没有递归树。额外分享一个避开大坑的小习惯最后多说一句。我自己在带别人做题时发现很多人的递归写错不是逻辑问题而是没有把“函数定义”清清楚楚说出口。反转链表这道题如果你能在心里准确说出“f(head)返回从head开始反转后的新头”后面所有代码就只是服务于这句话一旦你只是模模糊糊觉得“反转一下”写出来的代码大概率是错的。写递归题之前先自言自语把函数定义说一遍这句话值很多遍刷题。这个习惯对我自己帮助很大。每一道递归题我都要求自己在代码开头写一行注释直接注释出返回值是什么。有了这行注释终止条件怎么写、递归调用的返回值怎么用全都顺了。希望这篇拆解对你有用。三道题刷明白“递归”这两个字对你来说就不再是玄学而是一套可复用的思维工具。