递归这个坎几乎每个程序员都要迈。我见过不少自称“熟悉算法”的候选人让他画个链表反转没有问题一让他写递归就卡在终止条件上也见过工作几年的后端同事遇到目录遍历第一反应是开一个栈模拟循环而不是直接递归。所以我决定写一篇递归题目练习笔记不打算只堆题目答案而是想尽量把“为什么会这样递归”讲明白。这篇笔记适合准备算法面试、正在学数据结构、以及日常要在C语言或后端系统里写递归逻辑的人。我会从函数调用栈讲起用链表、二叉树、快速排序、递归最小二乘法、递归解析服务这些真实场景把递归从“玄学”变成“套路”。1. 真搞懂递归之前先把函数调用栈想清楚1.1 递归不是自己调用自己而是“栈上多了一层函数”很多初学者把递归背成“函数自己调用自己”这个说法方向对但没到本质。递归真正做的事是每次调用都向系统申请一个新的栈帧每个栈帧里保存着当前的参数、局部变量和返回地址。普通函数调用是A等B执行完再继续递归只是让函数在还没执行完的情况下又调用了同卵双生的另一个自己。你可以把一个递归函数想象成一层一层往下铺砖每一层都等待下一层的结果下一层又等待下一层的结果直到某一次调用直接返回不再往下铺这时候砖块才开始从最深处一块一块往上收。所以递归必须有一个“刹车”计算机术语里叫基准条件也叫终止条件。没有刹车的递归就是无限循环只不过循环是CPU跑满递归是栈空间写满最终抛出栈溢出。1.2 写递归的三要素我把递归题的解法收敛成三个问题练习时先问自己我的终止条件是什么最小的输入是什么直接就能给结果的那一类。我把问题拆分成了什么子问题整个问题的答案如何由子问题的答案组合出来。拆分后子问题是否和原问题是同一形态只有形态相同才能继续用同一个函数处理。举个例子输入一个正整数n要算n的阶乘。终止条件是 n 1 或 n 0直接返回1。拆分是 n! n * (n-1)!子问题和原问题一模一样只是参数小了1。于是代码就一清二楚int fact(int n) { if (n 1) return 1; return n * fact(n - 1); }很多刚上手的人把递归写错往往是因为一上来就盯着“我要返回什么”而不是先回答“哪一步开始不用再算了”。我在练习时强制自己先写终止条件再写递归体这个习惯帮我躲开了大半的坑。1.3 用斐波那契验证“信任递归函数”这个心态斐波那契是我最推荐的入门调试材料不是因为题目本身有用而是因为它能逼你接受一个心态调用递归函数时不要跳进下一层去模拟过程要假设下一层已经帮你算好了你现在只需要用它返回的结果去凑当前层的答案。int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }很多人拿到这段代码非要手动展开到fib(5)展开到fib(3)就开始头晕。正确的理解方式是fib(n - 1)和fib(n - 2)的返回值是别人替你算好的你只需要相加。这就是“信任递归”。信任建立不起来后面全排列、链表反转、快排都会写得扭扭捏捏。2. 三道必练递归题的完整思考记录2.1 链表反转先走到最后一个节点再回头链表反转是递归题里很经典的一道因为它会彻底颠覆你“从头开始处理”的直觉。链表的正常遍历方向是head到tail而递归反转的核心思路是先递归处理下一段链表让下一段反转好再把当前节点接到尾巴上。struct ListNode { int val; struct ListNode *next; }; struct ListNode* reverseList(struct ListNode* head) { if (head NULL || head-next NULL) { return head; } struct ListNode* newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }拿到这道题先不要想怎么一劳永逸反转整条链。假设当前节点是headhead后面的整段链表已经递归反转完毕那现在我该干什么只需要让head的下一个节点指回head再让head指向NULL就完成了当前节点的接入。终止条件就是“链表为空”或者“只剩一个节点”剩一个节点时它自己就是反转后的头。这个题练的是“从后往前处理”的递归思维。我练完后最大的收获是递归不一定都按原顺序处理数据有些场景天然适合从结果倒推回起点。2.2 二叉树最大深度左右子树结果如何合并二叉树最大深度的代码很短但它是理解“递归结果如何向上合并”的好样本。深度的一般定义是根节点到叶子节点的最长路径上的节点数也可以理解成一棵树的深度等于左子树深度和右子树深度中较大的那个再加1。int maxDepth(struct TreeNode* root) { if (root NULL) { return 0; } int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }这题的递归逻辑很纯粹先分别问左子树“你有多深”再问右子树“你有多深”当前节点做一次取最大值和加1的动作。子问题的形态和原问题完全一致所以可以放心递归。终止条件也很明确空节点深度为0。很多人会在这里纠结“为什么空节点的深度是0而不是1”我的建议是直接记住约定叶子节点的下一层是空空就没有节点所以是0。等你们学到树形DP和二叉树相关的大部分题目时会发现这个约定要继续沿用确认好基准条件定准了后面的递归才不会乱。2.3 全排列回溯式递归的“选择-撤销”模型全排列是递归练习里非常关键的一道题因为它是回溯算法的雏形。这里虽然也要递归但和“递去归来”稍微不同它一层层做选择选择到不能再选择就记录答案然后撤销选择返回上一层继续试别的路。def permute(nums): res [] n len(nums) used [False] * n def dfs(path): if len(path) n: res.append(path[:]) return for i in range(n): if used[i]: continue used[i] True path.append(nums[i]) dfs(path) path.pop() used[i] False dfs([]) return res全排列的递归里终止条件是路径长度等于数组长度。拆分方式是当前层先选一个没用过的数放到路径末尾剩下的排列交给下一层递归去生成。选完之后必须撤销也就是把刚加入的数弹出把标记改回False否则下一轮选择会互相污染。我早期写这个题经常漏掉path.pop()结果输出一堆重复排列。后来我给自己立了一条规矩回溯式递归里push和pop必须出现在同一个递归函数调用的前后对称位置。肿块只有一个你在哪里加入就在哪里移除。按照这个模型套组合、子集、N皇后这些题都能复用同一套思路。3. C语言递归实战快速排序递归实现的边界与性能3.1 C语言递归和高级语言递归相比差在哪练习C语言递归很多人会忽略一件事C的递归栈帧更轻量但更容易爆栈因为默认栈大小相对有限而且没有高级语言运行时的自动逃逸分析。C语言里每次函数调用都会在“调用栈”上分配一块空间保存返回地址、参数、局部变量。递归深度太大栈就爆了。高级语言里函数式语言会把某些递归优化成循环C的编译器虽然也做尾递归优化但前提是你能写出真正可以被优化的尾调用形式普通递归并不会自动变稳。不过这并不意味C不能练递归。恰恰相反C能让你更直观地看到每一层递归之间的数据传递。快速排序递归实现就是C语言递归最好的训练场之一因为要同时处理数组区间边界、元素交换和递归细分三个问题。3.2 快排递归实现选枢轴、分区间、递归两段以经典的单边挖坑法为例。快速排序的核心是先选一个枢轴pivot把数组分成“小于等于pivot”和“大于等于pivot”两块然后递归对左右两块分别排序。C语言代码可以这么写void quickSort(int arr[], int left, int right) { if (left right) { return; } int pivot arr[left]; int i left; int j right; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; } while (i j arr[i] pivot) { i; } if (i j) { arr[j--] arr[i]; } } arr[i] pivot; quickSort(arr, left, i - 1); quickSort(arr, i 1, right); }重点解释几个容易写错的细节终止条件是 left right而不是 left right。如果区间只有0个或1个元素就别再递归了。内层两个while必须加 i j 约束否则i或j会越界。从右侧找比pivot小的数为什么arr[j] pivot就继续j--因为等于pivot的元素可以留在原位不影响划分的正确性却可以减少交换次数。每一次递归传入的区间是[left, i - 1]和[i 1, right]枢轴i已经落在最终位置不需要再参与排序。我练这道题时犯过最典型的错误是把右区间写成[i, right]结果枢轴元素被反复拿出来排序无限递归直接栈溢出。写C递归时区间边界必须精确到“排除已归位元素”这对理解递归出口非常有帮助。3.3 快排递归的常见报错栈溢出、越界和重复比较用C语言跑快排递归我最常看到三种报错第一栈溢出。假如用一组已经排好序的数据每次都选最左边的数做枢轴那么每次只能分出一小部分和一个超长区间递归深度接近n栈很快就爆。解决办法是随机选枢轴或三数取中也可以用快速排序的非递归版本配合显式栈来模拟。第二越界访问。内层while不加ij判断很容易出现j一路扫描到数组左边之外。C语言不查边界越界后读到的是栈上的脏数据程序可能不崩溃但排序结果是错的。这种问题一旦出现最隐蔽的就是“偶尔错、偶尔对”。第三重复比较导致性能退化。这种不算报错但直接影响题目练习的体验。如果边界条件没有把枢轴排除左右递归区间重叠元素会被反复比较复杂度退化。我在做快排性能测试时发现只要把递归区间写成[left, i]和[i, right]顺序数据上的耗时立马肉眼可见地上升。C语言递归练习快排看起来是在练排序实际练的是“递归区间精确划分”。这些边界失误比起高级语言里的报错更隐蔽也更值得你耐心排查。4. 递归从“题目”走到“数学”递归最小二乘法的推导与实现4.1 从批量最小二乘到递推很多初学者觉得递归只会出现在代码里后来我在项目里看到“递归最小二乘法”这个词的时候发现这里的“递归”更多是数学递推的意思。所谓递推就是当前估计值在旧估计值的基础上加上一个修正量。最小二乘本来是一锤子买卖收集一批数据一次算出回归系数。但实际场景里数据是源源不断进来的每次来一个新样本就重新算一遍所有数据成本太高所以就有了递归形式。设要估计的参数是theta已有的协方差矩阵是P。普通最小二乘解是 theta (X^T X)^(-1) X^T y递归最小二乘则希望通过新样本(x, y)不断修正theta不需要保留历史数据也能逼近同样的结果。这条路线对实时控制、在线估计、信号处理特别有用。4.2 递推公式是怎么来的递归最小二乘的核心是增量更新。我在这里用一个标量示例说明便于理解。设系统满足 y x * thetax是输入y是观测值theta是待估参数。更新过程分三步计算增益系数K用误差 (y - x * theta) 修正thetatheta_new theta_old K * (y - x * theta_old)更新P矩阵。增益k的计算里包含遗忘因子lambdalambda通常取0.9到1之间。lambda越接近1历史数据影响越大估计越平滑lambda越小越看重新样本跟踪变化越快但噪声也越明显。为了让读者不困在矩阵推导里我直接用Python写一个单参数版本。多参数版本公式结构完全一样只是把x变成向量theta变成向量P变成矩阵。class RLS: def __init__(self, theta00.0, p01.0, lam0.98): self.theta theta0 self.P p0 self.lam lam def update(self, x, y): # 增益 K self.P * x / (self.lam x * self.P * x) # 修正参数 self.theta K * (y - x * self.theta) # 更新协方差 self.P (1 - K * x) * self.P / self.lam return self.theta4.3 递推估计过程演示用一段简单的数据验证假设真实theta是3观测值有噪声rls RLS(theta00.0, p01.0, lam0.98) for i in range(200): x i % 10 1 y 3 * x random.uniform(-0.5, 0.5) theta_est rls.update(x, y) print(theta_est)跑下来theta会从0慢慢靠近3不会完全等于3因为噪声始终存在但围绕3波动的幅度会越来越小。这个案例让我觉得“递归”在数学里是一种在线优化结构和代码里的递归函数不完全是一回事但有共同之处每一步都在前一步结果的基础上往前推进一步。如果做矩阵版本需要注意theta0和P0的初始化。P0越大说明初始估计越不可靠前几步修正幅度越大P0太小收敛会非常慢。这是一个典型的算法调试经验不跑一遍很难形成手感。4.4 数学递推和程序递归的边界递归最小二乘里的“递归”翻译自recursive对应的是“递推”不是“recursion”和函数自己调用自己没有必然关系。我把这个放在练习笔记里是想提醒大家搜索“递归”关键词时会看到两种完全不同的用法。一个是编程概念里的recursion一个是信号处理和控制论里的recursive estimation。看到题目时先分辨清楚否则会拿错思考工具。练习角度来说递归最小二乘更接近“递推公式实现”它需要用循环或迭代器逐样本更新状态而不是写一个函数不停调用自己。但你在理解它时同样会用到“子问题”的思想新状态是旧状态加上修正量这就是一个递推子问题。5. 真实系统里的递归递归解析服务的查询链5.1 递归解析服务解决什么问题“递归解析服务”在真实世界里最常见的是域名系统里的递归查询。我去理解它的时候发现它就是典型的“把大问题拆成多个子问题逐层确认”的过程。当用户输入一个域名设备本身只知道根服务器在哪、顶级域名服务器地址从哪能问到不可能知道所有域名的最终IP。递归解析服务就是那个“跑腿者”它替客户端向多级服务器发起查询直到拿到最终IP再返回给客户端。对终端用户来说它只发出一个请求然后拿到一个结果中间的层层递归对用户透明。5.2 一个域名查询要经过几层递归以访问 www.example.com 为例。递归解析服务先看缓存里有没有答案没有就向根服务器问“com域名的权威服务器在哪”然后向com权威服务器问“example.com的权威服务器在哪”最后向example.com的权威服务器问“www的主机记录是什么”。每一层返回的都是“下一站地址”或“最终答案”递归解析器把这些结果一级一级组装回来。这个过程看起来和二叉树递归很像每一层只负责一个相对局部的判断最终结果由底层返回的数据向上传递。如果中途某一层没有答案要么继续往下追要么返回一个“不存在”的标记相当于终止条件。工程上递归解析服务通常要设置超时时间、次数上限、缓存有效期防止某个上游卡住导致整个查询链吊死。5.3 和写题目里的递归有什么关联练递归题对你的业务能力帮助最直接的体现就是这种地方。你在题目里学到的终止条件、递归深度、缓存复用映射到递归解析服务里对应的是TTL缓存、查询上限和超时降级。我在一个内部系统里设计配置文件解析器时遇到过递归解析的坑配置项之间可以互相引用类似A引用了BB又引用了C。如果不限制深度循环引用会让解析器无限递归下去。后来我参考递归题里的“visited集合”思路给每个配置文件加一个解析状态正在解析中的项如果再次出现直接判定为循环依赖并报错。这个方案比单纯限制递归深度要好因为它能给出明确错误信息而不是干巴巴的“解析超深”。所以递归练习不是只为了面试而是为了在真实系统里遇到“层级嵌套、循环引用、逐层查询”时你能下意识地判断出该用什么手段防御。6. 练习后复盘把递归练成肌肉记忆的六条心法6.1 第一招所有递归题先写终止条件不管题目多复杂我的顺序永远是终止条件放最前。空指针、空数组、单节点、n0都是最容易被忽略但又最能防栈溢出的点。很多初学者看完一段递归代码觉得“看懂了”自己手写却总在边界出错就是因为没把终止条件当成规定动作。6.2 第二招不要跟踪每一层递归跟踪递归是新手最容易踩的坑。我后来给自己定了一个规则递归函数的返回值直接当作一个已知数使用除非调试必要否则不展开。如果实在需要验证递归过程就打印日志把参数和返回值打出来之后对照输出理解执行流而不是在脑子里“人肉CPU”。6.3 第三招小数据样本跑通题目写完先用最小规模输入跑逐步扩大。链表反转可以用3个节点二叉树深度可以用一层和两层树快排可以用5个数的乱序数组。小数据跑通之后再上大数据压性能。这个习惯帮我避开过很多“在小数据上偶然对、大数据上栈溢出”的尴尬情况。6.4 第四招栈溢出不一定是死循环很多人一看到栈溢出就条件反射认为是无限递归其实还有可能是递归深度本身太大比如在极端退化的快排里。这个时候要优化递归深度而不是简单怀疑逻辑错误。逻辑错误的特征是输出结果不对栈溢出的特征是程序还没跑完就崩两者排查方法完全不同。6.5 第五招把递归改成迭代来互相验证递归代码通常更短但迭代代码更容易控制栈。我练习时会故意把同一道题用两种方式实现递归写法帮助理清逻辑迭代写法帮助确认边界。二叉树的前序遍历用递归写一遍再用栈模拟写一遍做完之后能明显感觉到自己对“函数调用栈”的理解上了一个台阶。6.6 第六招倒背经典递归模板递归题里很多结构是重复的。链表题套路是“递归处理后续节点再处理当前节点”二叉树题套路是“先递归左子树再递归右子树在回溯时合并”回溯题套路是“选择、递归、撤销”。我把这些模板倒背到形成条件反射再看到新题就能快速定位“它属于哪一类”。我自己练完这些题目之后最大的变化不是能默写快排和全排列而是写代码前会自动思考“这个函数的返回值代表什么”“什么时候应该停止递归”。这种思考方式远比记住题目答案有价值。你会慢慢发现很多看似不相关的场景比如解析嵌套JSON、遍历菜单树、计算组织架构层级底层都是同一套递归模型。把这些心法用熟练下次再遇到递归题目它就不再是“看运气会不会”而是“必定能拆解清楚”的问题。