1. 为什么我劝你先啃下递归这块硬骨头很多刚开始刷算法题的朋友一看到“递归”两个字就觉得头大。说实话我当年第一次接触递归的时候对着屏幕上那个不断调用自己的函数发呆了一下午脑子里全是“这玩意儿到底怎么停下来的”。后来带队打比赛、辅导学弟学妹发现几乎每个人都会在这一关卡上栽跟头。但递归恰恰是算法竞赛里绕不开的基石——搜索、分治、动态规划、树和图的各种遍历哪一样都离不开递归思想。这篇内容就是给刚入门的你准备的递归初阶拆解。我不打算堆一堆抽象概念而是拿竞赛里最容易出现的几类问题一步步带你把“递归到底在干嘛”这件事彻底搞明白。看完你至少能掌握三件事递归函数的写法套路、递归终止条件的设置技巧、以及如何把递归过程在脑子里画出来。不管是刚接触C或Java的算法小白还是想系统梳理递归基础的参赛选手这篇文章都能让你少走很多弯路。2. 递归的本质一个函数如何优雅地调用自己2.1 别再死磕“调用自己”这四个字很多教材一上来就说“递归就是函数调用自己”这句话本身没错但它特别容易把人带偏。你如果脑子里一直想着“一个函数怎么调用自己”就会陷入无限套娃的恐惧中。我更喜欢把递归理解成“把一个大规模问题拆成若干个规模更小的同类问题”。举个生活化的例子。假设你面前有一队人你想知道排在第10个的是谁。如果第1个人告诉你“我就是第1个”那么第2个人只需要知道前一个是第1个就能推出自己是第2个。以此类推第10个人只需要知道前面那个人是第9个就能推出自己是第10个。这里每一个人都在做同一件事——根据前一个人的位置算出自己的位置。这其实就是递归的味道同一个动作不断重复但每次面对的数据规模在缩小。在计算机里递归函数就是这种“重复但规模递减”的过程。函数每次调用自己时都会带着一组更小的参数直到参数小到某个临界点直接返回一个已知答案然后一层一层把结果传回去。2.2 递归的两个核心构件递推关系与终止条件写递归函数本质上就是回答两个问题第一个问题当前这一步和下一步之间的关系是什么比如算n的阶乘n! n * (n-1)!这就是递推关系。第二个问题什么时候可以停止递归比如0! 1这就是终止条件。这两个构件少一个都不行。没有递推关系函数不知道怎么往下走没有终止条件函数就会无限调用自己最终栈溢出程序直接崩掉。很多初学者写递归报错十有八九是终止条件没写对或者没写全。我建议你在写任何递归函数之前先在注释里把这两行写清楚边界条件是什么递推公式是什么。这不是浪费时间而是帮你理清思路。代码写起来反而会更快。2.3 递归的执行过程从“递”到“归”的完整旅程光说不练假把式。我们拿最简单的例子——计算斐波那契数列第n项——来走一遍递归的全过程。斐波那契数列的定义是f(1) 1f(2) 1f(n) f(n-1) f(n-2)。假设我们要算f(5)程序执行顺序是这样的调用f(5)检测到5既不是1也不是2于是需要f(4)和f(3)想算f(4)检测到4不满足终止条件于是需要f(3)和f(2)想算f(3)检测到3不满足终止条件于是需要f(2)和f(1)这时f(2)直接返回1f(1)直接返回1于是f(3) 1 1 2拿到f(3)后继续算f(2)f(2)直接返回1于是f(4) 2 1 3现在f(4)有了接着需要算f(3)f(3)在上面已经算过一次但递归不会记住结果于是又从头算了一遍f(3) 2最终f(5) f(4) f(3) 3 2 5这个过程中“递”是从f(5)一路深入到f(2)、f(1)的过程“归”是拿到最小问题的答案后逐步返回、逐层计算的过程。你不必把这个过程背下来但一定要理解递归不是同步算出所有结果的而是先一路走到最深处再一层一层往回走。提示在初学阶段试着在纸上手动展开f(5)的调用树标出每个函数调用的先后顺序。这个方法虽然笨但对建立递归直觉非常有效。3. 递归初阶的三大经典题型拆解3.1 阶乘与累加理解递归的最小单元阶乘是递归入门绕不开的例子。fact(n) n * fact(n-1)边界条件是fact(1) 1。代码写出来非常短但它包含了递归的所有要素。int fact(int n) { if (n 1) return 1; // 终止条件 return n * fact(n - 1); // 递推关系 }累加也是同样的套路。sum(n) n sum(n-1)边界条件是sum(0) 0。这类问题简单到几乎一眼就能看穿但请你千万别嫌它简单。我见过太多人一上来就刷回溯、树形DP结果连最简单的递归展开都画不标准。基础打不牢后面真的会很难受。这里有个值得思考的细节为什么阶乘的边界条件用n 1而不是n 0如果你把n 0也加进去定义成fact(0) 1程序也能跑而且从数学定义上更严谨。但使用n 1作为边界可以少一层函数调用。竞赛里虽然不差这一层但这种对边界条件精打细算的习惯到了追求极致性能的题上就有意义了。3.2 汉诺塔递归思想的经典试金石汉诺塔问题描述起来很简单有三根柱子A、B、CA柱上有n个大小不同的圆盘从下往上依次变小。要求把A柱上所有圆盘移到C柱每次只能移动一个圆盘且大盘不能压在小盘上。如果你尝试用循环去模拟这个移动过程会发现极其复杂。但用递归来想一句话就能说清楚把上面的n-1个盘子从A移到B借助C把最大的盘子从A移到C再把B上的n-1个盘子移到C借助A。void hanoi(int n, char from, char helper, char to) { if (n 1) { cout from - to endl; return; } hanoi(n - 1, from, to, helper); cout from - to endl; hanoi(n - 1, helper, from, to); }这段代码只有短短九行但它完美展示了递归最核心的思维方式你不需要关心n-1个盘子具体是怎么移动的你只需要假设“递归函数已经能完成这件事”然后用它来描述当前这一步。汉诺塔的递归解法之所以经典就是因为它强迫你学会“信任”递归——这种信任感是后面写复杂搜索算法时必备的。我第一次看这段代码时始终想不通为什么中间的移动直接打印from到to就行了不需要递归。后来才明白中间这一步移动的是当前层最大的那个盘子它之上没有任何盘子所以可以一步到位。3.3 全排列生成从递归到回溯的过渡全排列是递归初阶到中阶的一道门槛。给定一个数组要求输出所有可能的排列方式。比如数组[1, 2, 3]所有排列是123、132、213、231、312、321。全排列的递归思路是依次固定每一位然后对剩余部分做全排列。固定第1位时有3种选择每种选择下固定第2位时剩下2种选择最后一位没有选择。这个过程用递归写起来非常直观。void permute(vectorint nums, int start) { if (start nums.size()) { // 输出当前排列 for (int x : nums) cout x ; cout endl; return; } for (int i start; i nums.size(); i) { swap(nums[start], nums[i]); permute(nums, start 1); swap(nums[start], nums[i]); // 回溯恢复原状 } }这一段代码实际上已经是回溯算法的雏形了。注意其中最后一行swap的作用当递归返回时数组必须恢复到进入递归之前的状态否则后面的排列就会错乱。这个“恢复现场”的操作就是回溯算法名字的来源。注意全排列的递归实现里忘记把交换过的元素换回来是最常见的错误。排查的时候先看每次进入下一层递归前数组状态是否和预期一致。4. 递归进阶前的关键认知递归与栈的底层关系4.1 每一次函数调用都是一次入栈很多人在刚学递归时都会有一个困惑这么多层调用计算机是怎么记住每层状态的答案就是栈。操作系统为每次函数调用分配一段栈空间用来保存函数的局部变量、参数和返回地址。递归调用本质上是同一个函数的多次入栈。以阶乘fact(3)为例第一次调用fact(3)参数3入栈fact(3)内部调用fact(2)参数2入栈fact(2)内部调用fact(1)参数1入栈fact(1)返回1参数1出栈fact(2)拿到返回值后算出2出栈fact(3)拿到返回值后算出6出栈这个过程像不像一摞盘子先放下的盘子最后才能拿起来后放下的盘子最先被拿起来。这就是“后进先出”的栈结构。4.2 递归深度与栈溢出的关系既然递归需要消耗栈空间那么递归层数太多栈空间就会被耗尽程序就会崩溃这就是栈溢出。竞赛里C默认的栈空间通常在数MB级别每层递归消耗的栈空间取决于局部变量多少。一个简单的递归函数每层可能消耗几十字节到几百字节。粗略估算几万层递归大概率就会爆栈。所以在竞赛里你会发现递归深度超过一万的题目很多人会改用循环或者显式栈来模拟递归。这不是说递归不好而是任何工具都有它的边界。理解了这层关系你就不会写出一个递归十万层的函数然后干瞪眼。4.3 递归转循环手工模拟栈的思路当你理解了递归背后是栈之后很多所谓的高深技巧就变得自然了。比如某些题目要求你不能用递归这时候你可以用一个std::stack来手动模拟递归的过程。拿二叉树的先序遍历举例。递归版本非常简洁void preorder(TreeNode* root) { if (root nullptr) return; visit(root-val); preorder(root-left); preorder(root-right); }改成非递归版本stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* cur stk.top(); stk.pop(); if (cur nullptr) continue; visit(cur-val); stk.push(cur-right); stk.push(cur-left); }注意这里入栈顺序和递归顺序的关系递归是先访问左子树再访问右子树而栈是后进先出所以为了先访问左子树就要先把右子树压入栈再压入左子树。这个细节是很多人的困惑点想通了就明白了。5. 递归学习路上的常见错误与排查技巧5.1 没有终止条件或终止条件不可达这是新手最容易踩的坑。写递归时只想着递推关系忘了边界条件或者边界条件写错导致递归永远无法结束。例如计算斐波那契数列时如果不处理n等于1和2的情况函数就会一路向负数递归下去直到栈溢出。排查方法很简单在递归函数入口处打印当前参数值观察参数是否在向边界方向收敛。如果参数没有变小或者没有向边界靠拢那问题基本就出在递推关系上。5.2 递归函数返回值的使用方式不对有些递归函数需要返回值有些只需要在递归过程中处理全局变量这两种混用时很容易出错。我见过一个常见的错误函数定义成int类型但递归调用时忘记接收返回值直接把递归调用当成语句执行了。int dfs(int n) { int ans 0; if (n 1) return 1; ans dfs(n - 1) n; // 这里必须接收返回值 return ans; }建议在初学阶段统一思想需要返回值的递归函数每一层的所有路径上都必须保证最终有return语句。编译器通常会对这种情况给警告但警告容易被忽略自己检查时一定要细心。5.3 全局变量与递归的相互作用递归配合全局变量用起来很爽但也容易出问题。比如在全排列问题中如果用全局数组记录排列结果那么每次递归修改全局数组后返回时必须恢复现场。这个恢复操作一旦遗漏数据就会被前面的递归分支污染。排查技巧在每次递归调用的前后打印整个数组的状态。如果发现返回后数据没有被还原问题就出在缺少回溯操作上。5.4 递归深度过大导致的时序问题当递归深度比较大时输出信息的顺序会变得很难追踪。调试时建议不要在每一层打印详细信息而是只打印进入和离开时的关键参数这样日志会清爽很多也更容易定位问题。我自己的调试习惯是每个递归函数入口处打印“进入 nxxx”出口处打印“离开 nxxx返回值为xxx”。这样整个递归过程就像一张调用时间线哪一层出了问题一目了然。提示写递归时先在纸上把终止条件和递推关系写明白再动手写代码。这是所有竞赛选手的基本功。6. 从递归初阶走向竞赛实战的建议6.1 递归能力的三个层次以我带过的选手经验来看递归能力可以粗略分成三个层次。第一层是能看懂递归代码知道它在干什么。第二层是能自己写简单的递归函数处理阶乘、斐波那契、汉诺塔这类问题。第三层是能把递归思维迁移到搜索、分治、动态规划等更复杂的算法中。大多数人卡在第二层到第三层之间的过渡。这很正常因为第三层需要大量练习和题型积累。但好消息是递归这个思维的迁移路径是非常清晰的你只要在入门阶段把前面的基础题型吃透后面学习DFS、BFS、回溯、树形DP时很多概念就是顺水推舟的事。6.2 入门阶段的高效练习顺序我建议按照这个顺序来刷递归相关题目阶乘、斐波那契数列练习最基础的递归框架字符串反转或数组求和练习带返回值的递归汉诺塔练习多参数递归和函数体内多次递归调用全排列、子集生成练习递归与回溯的结合二叉树遍历练习递归在数据结构上的应用每类题不用刷太多两三道经典的吃透就够了。关键是每一道题都要做到能画出递归调用的过程图能说清楚每一层的参数变化能解释为什么终止条件是对的。6.3 竞赛场景下的递归优化意识入门阶段虽然不需要过分优化但你最好从一开始就养成几个好习惯。第一个习惯是警惕重复计算比如斐波那契数列的朴素递归会有大量重复子问题入门阶段知道这一点就够了后续学习记忆化搜索就能解决。第二个习惯是注意递归深度遇到深度可能很大的问题提前考虑是否需要转成非递归。第三个习惯是计算复杂度递归函数的时间复杂度分析方法和普通循环不同需要根据递归调用次数来判断。这些习惯不会让你立刻变强但会让你在后续学习更高级算法时不那么痛苦。很多人在分治和DP上吃亏追溯起来都是递归基本功不扎实。6.4 一个可复制的入门练习模板最后分享一个我常用的练习模板。每次学一个新递归题我会强制自己回答以下四个问题这个函数的功能是什么输入是什么输出是什么递推关系是什么如何把当前问题拆成更小的同类问题边界条件是什么最小规模的问题怎么直接解决递归调用的顺序是什么多个递归调用之间有没有先后依赖回答完这四个问题再写代码成功率会高很多。这套方法不仅适用于递归几乎所有算法题都可以用这个思路来拆解。我个人在实际带新人时的体会是递归不是靠看会的而是靠画图和手写练会的。哪怕代码再简单也一定要亲手写在纸上把每一层调用的参数变化标出来。这个过程虽然耗时但远比盯着屏幕发呆有效得多。当你某天突然发现自己能一眼看穿某道回溯题的递归结构时你会感谢当初那个肯花时间打基础、老老实实画调用树的自己。 
长河君 · 2026/10/21 10:03:46 · 阅读 1.2k 递归算法入门：递推关系与终止条件的核心原理及经典题型拆解
1. 为什么我劝你先啃下递归这块硬骨头很多刚开始刷算法题的朋友一看到“递归”两个字就觉得头大。说实话我当年第一次接触递归的时候对着屏幕上那个不断调用自己的函数发呆了一下午脑子里全是“这玩意儿到底怎么停下来的”。后来带队打比赛、辅导学弟学妹发现几乎每个人都会在这一关卡上栽跟头。但递归恰恰是算法竞赛里绕不开的基石——搜索、分治、动态规划、树和图的各种遍历哪一样都离不开递归思想。这篇内容就是给刚入门的你准备的递归初阶拆解。我不打算堆一堆抽象概念而是拿竞赛里最容易出现的几类问题一步步带你把“递归到底在干嘛”这件事彻底搞明白。看完你至少能掌握三件事递归函数的写法套路、递归终止条件的设置技巧、以及如何把递归过程在脑子里画出来。不管是刚接触C或Java的算法小白还是想系统梳理递归基础的参赛选手这篇文章都能让你少走很多弯路。2. 递归的本质一个函数如何优雅地调用自己2.1 别再死磕“调用自己”这四个字很多教材一上来就说“递归就是函数调用自己”这句话本身没错但它特别容易把人带偏。你如果脑子里一直想着“一个函数怎么调用自己”就会陷入无限套娃的恐惧中。我更喜欢把递归理解成“把一个大规模问题拆成若干个规模更小的同类问题”。举个生活化的例子。假设你面前有一队人你想知道排在第10个的是谁。如果第1个人告诉你“我就是第1个”那么第2个人只需要知道前一个是第1个就能推出自己是第2个。以此类推第10个人只需要知道前面那个人是第9个就能推出自己是第10个。这里每一个人都在做同一件事——根据前一个人的位置算出自己的位置。这其实就是递归的味道同一个动作不断重复但每次面对的数据规模在缩小。在计算机里递归函数就是这种“重复但规模递减”的过程。函数每次调用自己时都会带着一组更小的参数直到参数小到某个临界点直接返回一个已知答案然后一层一层把结果传回去。2.2 递归的两个核心构件递推关系与终止条件写递归函数本质上就是回答两个问题第一个问题当前这一步和下一步之间的关系是什么比如算n的阶乘n! n * (n-1)!这就是递推关系。第二个问题什么时候可以停止递归比如0! 1这就是终止条件。这两个构件少一个都不行。没有递推关系函数不知道怎么往下走没有终止条件函数就会无限调用自己最终栈溢出程序直接崩掉。很多初学者写递归报错十有八九是终止条件没写对或者没写全。我建议你在写任何递归函数之前先在注释里把这两行写清楚边界条件是什么递推公式是什么。这不是浪费时间而是帮你理清思路。代码写起来反而会更快。2.3 递归的执行过程从“递”到“归”的完整旅程光说不练假把式。我们拿最简单的例子——计算斐波那契数列第n项——来走一遍递归的全过程。斐波那契数列的定义是f(1) 1f(2) 1f(n) f(n-1) f(n-2)。假设我们要算f(5)程序执行顺序是这样的调用f(5)检测到5既不是1也不是2于是需要f(4)和f(3)想算f(4)检测到4不满足终止条件于是需要f(3)和f(2)想算f(3)检测到3不满足终止条件于是需要f(2)和f(1)这时f(2)直接返回1f(1)直接返回1于是f(3) 1 1 2拿到f(3)后继续算f(2)f(2)直接返回1于是f(4) 2 1 3现在f(4)有了接着需要算f(3)f(3)在上面已经算过一次但递归不会记住结果于是又从头算了一遍f(3) 2最终f(5) f(4) f(3) 3 2 5这个过程中“递”是从f(5)一路深入到f(2)、f(1)的过程“归”是拿到最小问题的答案后逐步返回、逐层计算的过程。你不必把这个过程背下来但一定要理解递归不是同步算出所有结果的而是先一路走到最深处再一层一层往回走。提示在初学阶段试着在纸上手动展开f(5)的调用树标出每个函数调用的先后顺序。这个方法虽然笨但对建立递归直觉非常有效。3. 递归初阶的三大经典题型拆解3.1 阶乘与累加理解递归的最小单元阶乘是递归入门绕不开的例子。fact(n) n * fact(n-1)边界条件是fact(1) 1。代码写出来非常短但它包含了递归的所有要素。int fact(int n) { if (n 1) return 1; // 终止条件 return n * fact(n - 1); // 递推关系 }累加也是同样的套路。sum(n) n sum(n-1)边界条件是sum(0) 0。这类问题简单到几乎一眼就能看穿但请你千万别嫌它简单。我见过太多人一上来就刷回溯、树形DP结果连最简单的递归展开都画不标准。基础打不牢后面真的会很难受。这里有个值得思考的细节为什么阶乘的边界条件用n 1而不是n 0如果你把n 0也加进去定义成fact(0) 1程序也能跑而且从数学定义上更严谨。但使用n 1作为边界可以少一层函数调用。竞赛里虽然不差这一层但这种对边界条件精打细算的习惯到了追求极致性能的题上就有意义了。3.2 汉诺塔递归思想的经典试金石汉诺塔问题描述起来很简单有三根柱子A、B、CA柱上有n个大小不同的圆盘从下往上依次变小。要求把A柱上所有圆盘移到C柱每次只能移动一个圆盘且大盘不能压在小盘上。如果你尝试用循环去模拟这个移动过程会发现极其复杂。但用递归来想一句话就能说清楚把上面的n-1个盘子从A移到B借助C把最大的盘子从A移到C再把B上的n-1个盘子移到C借助A。void hanoi(int n, char from, char helper, char to) { if (n 1) { cout from - to endl; return; } hanoi(n - 1, from, to, helper); cout from - to endl; hanoi(n - 1, helper, from, to); }这段代码只有短短九行但它完美展示了递归最核心的思维方式你不需要关心n-1个盘子具体是怎么移动的你只需要假设“递归函数已经能完成这件事”然后用它来描述当前这一步。汉诺塔的递归解法之所以经典就是因为它强迫你学会“信任”递归——这种信任感是后面写复杂搜索算法时必备的。我第一次看这段代码时始终想不通为什么中间的移动直接打印from到to就行了不需要递归。后来才明白中间这一步移动的是当前层最大的那个盘子它之上没有任何盘子所以可以一步到位。3.3 全排列生成从递归到回溯的过渡全排列是递归初阶到中阶的一道门槛。给定一个数组要求输出所有可能的排列方式。比如数组[1, 2, 3]所有排列是123、132、213、231、312、321。全排列的递归思路是依次固定每一位然后对剩余部分做全排列。固定第1位时有3种选择每种选择下固定第2位时剩下2种选择最后一位没有选择。这个过程用递归写起来非常直观。void permute(vectorint nums, int start) { if (start nums.size()) { // 输出当前排列 for (int x : nums) cout x ; cout endl; return; } for (int i start; i nums.size(); i) { swap(nums[start], nums[i]); permute(nums, start 1); swap(nums[start], nums[i]); // 回溯恢复原状 } }这一段代码实际上已经是回溯算法的雏形了。注意其中最后一行swap的作用当递归返回时数组必须恢复到进入递归之前的状态否则后面的排列就会错乱。这个“恢复现场”的操作就是回溯算法名字的来源。注意全排列的递归实现里忘记把交换过的元素换回来是最常见的错误。排查的时候先看每次进入下一层递归前数组状态是否和预期一致。4. 递归进阶前的关键认知递归与栈的底层关系4.1 每一次函数调用都是一次入栈很多人在刚学递归时都会有一个困惑这么多层调用计算机是怎么记住每层状态的答案就是栈。操作系统为每次函数调用分配一段栈空间用来保存函数的局部变量、参数和返回地址。递归调用本质上是同一个函数的多次入栈。以阶乘fact(3)为例第一次调用fact(3)参数3入栈fact(3)内部调用fact(2)参数2入栈fact(2)内部调用fact(1)参数1入栈fact(1)返回1参数1出栈fact(2)拿到返回值后算出2出栈fact(3)拿到返回值后算出6出栈这个过程像不像一摞盘子先放下的盘子最后才能拿起来后放下的盘子最先被拿起来。这就是“后进先出”的栈结构。4.2 递归深度与栈溢出的关系既然递归需要消耗栈空间那么递归层数太多栈空间就会被耗尽程序就会崩溃这就是栈溢出。竞赛里C默认的栈空间通常在数MB级别每层递归消耗的栈空间取决于局部变量多少。一个简单的递归函数每层可能消耗几十字节到几百字节。粗略估算几万层递归大概率就会爆栈。所以在竞赛里你会发现递归深度超过一万的题目很多人会改用循环或者显式栈来模拟递归。这不是说递归不好而是任何工具都有它的边界。理解了这层关系你就不会写出一个递归十万层的函数然后干瞪眼。4.3 递归转循环手工模拟栈的思路当你理解了递归背后是栈之后很多所谓的高深技巧就变得自然了。比如某些题目要求你不能用递归这时候你可以用一个std::stack来手动模拟递归的过程。拿二叉树的先序遍历举例。递归版本非常简洁void preorder(TreeNode* root) { if (root nullptr) return; visit(root-val); preorder(root-left); preorder(root-right); }改成非递归版本stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* cur stk.top(); stk.pop(); if (cur nullptr) continue; visit(cur-val); stk.push(cur-right); stk.push(cur-left); }注意这里入栈顺序和递归顺序的关系递归是先访问左子树再访问右子树而栈是后进先出所以为了先访问左子树就要先把右子树压入栈再压入左子树。这个细节是很多人的困惑点想通了就明白了。5. 递归学习路上的常见错误与排查技巧5.1 没有终止条件或终止条件不可达这是新手最容易踩的坑。写递归时只想着递推关系忘了边界条件或者边界条件写错导致递归永远无法结束。例如计算斐波那契数列时如果不处理n等于1和2的情况函数就会一路向负数递归下去直到栈溢出。排查方法很简单在递归函数入口处打印当前参数值观察参数是否在向边界方向收敛。如果参数没有变小或者没有向边界靠拢那问题基本就出在递推关系上。5.2 递归函数返回值的使用方式不对有些递归函数需要返回值有些只需要在递归过程中处理全局变量这两种混用时很容易出错。我见过一个常见的错误函数定义成int类型但递归调用时忘记接收返回值直接把递归调用当成语句执行了。int dfs(int n) { int ans 0; if (n 1) return 1; ans dfs(n - 1) n; // 这里必须接收返回值 return ans; }建议在初学阶段统一思想需要返回值的递归函数每一层的所有路径上都必须保证最终有return语句。编译器通常会对这种情况给警告但警告容易被忽略自己检查时一定要细心。5.3 全局变量与递归的相互作用递归配合全局变量用起来很爽但也容易出问题。比如在全排列问题中如果用全局数组记录排列结果那么每次递归修改全局数组后返回时必须恢复现场。这个恢复操作一旦遗漏数据就会被前面的递归分支污染。排查技巧在每次递归调用的前后打印整个数组的状态。如果发现返回后数据没有被还原问题就出在缺少回溯操作上。5.4 递归深度过大导致的时序问题当递归深度比较大时输出信息的顺序会变得很难追踪。调试时建议不要在每一层打印详细信息而是只打印进入和离开时的关键参数这样日志会清爽很多也更容易定位问题。我自己的调试习惯是每个递归函数入口处打印“进入 nxxx”出口处打印“离开 nxxx返回值为xxx”。这样整个递归过程就像一张调用时间线哪一层出了问题一目了然。提示写递归时先在纸上把终止条件和递推关系写明白再动手写代码。这是所有竞赛选手的基本功。6. 从递归初阶走向竞赛实战的建议6.1 递归能力的三个层次以我带过的选手经验来看递归能力可以粗略分成三个层次。第一层是能看懂递归代码知道它在干什么。第二层是能自己写简单的递归函数处理阶乘、斐波那契、汉诺塔这类问题。第三层是能把递归思维迁移到搜索、分治、动态规划等更复杂的算法中。大多数人卡在第二层到第三层之间的过渡。这很正常因为第三层需要大量练习和题型积累。但好消息是递归这个思维的迁移路径是非常清晰的你只要在入门阶段把前面的基础题型吃透后面学习DFS、BFS、回溯、树形DP时很多概念就是顺水推舟的事。6.2 入门阶段的高效练习顺序我建议按照这个顺序来刷递归相关题目阶乘、斐波那契数列练习最基础的递归框架字符串反转或数组求和练习带返回值的递归汉诺塔练习多参数递归和函数体内多次递归调用全排列、子集生成练习递归与回溯的结合二叉树遍历练习递归在数据结构上的应用每类题不用刷太多两三道经典的吃透就够了。关键是每一道题都要做到能画出递归调用的过程图能说清楚每一层的参数变化能解释为什么终止条件是对的。6.3 竞赛场景下的递归优化意识入门阶段虽然不需要过分优化但你最好从一开始就养成几个好习惯。第一个习惯是警惕重复计算比如斐波那契数列的朴素递归会有大量重复子问题入门阶段知道这一点就够了后续学习记忆化搜索就能解决。第二个习惯是注意递归深度遇到深度可能很大的问题提前考虑是否需要转成非递归。第三个习惯是计算复杂度递归函数的时间复杂度分析方法和普通循环不同需要根据递归调用次数来判断。这些习惯不会让你立刻变强但会让你在后续学习更高级算法时不那么痛苦。很多人在分治和DP上吃亏追溯起来都是递归基本功不扎实。6.4 一个可复制的入门练习模板最后分享一个我常用的练习模板。每次学一个新递归题我会强制自己回答以下四个问题这个函数的功能是什么输入是什么输出是什么递推关系是什么如何把当前问题拆成更小的同类问题边界条件是什么最小规模的问题怎么直接解决递归调用的顺序是什么多个递归调用之间有没有先后依赖回答完这四个问题再写代码成功率会高很多。这套方法不仅适用于递归几乎所有算法题都可以用这个思路来拆解。我个人在实际带新人时的体会是递归不是靠看会的而是靠画图和手写练会的。哪怕代码再简单也一定要亲手写在纸上把每一层调用的参数变化标出来。这个过程虽然耗时但远比盯着屏幕发呆有效得多。当你某天突然发现自己能一眼看穿某道回溯题的递归结构时你会感谢当初那个肯花时间打基础、老老实实画调用树的自己。