递归Recursion可以说是 C 语言初学阶段最容易让思维绕不过弯的知识点。函数自己调用自己那不是无限循环吗今天我们从零开始彻底把递归这件事弄清楚——从基本概念到经典面试题一条龙安排。零、递归是什么—— 先看一个神奇的比喻想象你面前有两面镜子面对面放着。你往中间一站——镜子里面出现了无数个你从小到大一层套一层无限延伸。递归就是这种「自己包含自己」的思想。在编程里「递归」就是一个函数在执行过程中自己调用自己。先来感受一个最简单的递归函数voidhello(){printf(hello\n);hello();// 自己调用自己}这个函数做了什么打印一句 “hello”然后调用它自己。它自己又打印一句 “hello”又调用它自己……无限循环。当然这个例子是反面教材——没有停下来的条件会一直跑到程序崩溃。但它让你直观地看到了哦原来递归就是函数自己调自己。一、递归的正确打开方式两个必要条件一个「能用」的递归必须同时具备两个条件条件一递归出口什么时候停下来就像你从一栋楼往下走楼梯你必须知道「走到一楼就停」。如果没有出口你就走进地下室、地基、地心……永远走不到头。在代码里「递归出口」就是if判断当满足某个条件时不再调用自己直接返回结果。条件二递推公式每一步怎么走到下一步你往下走楼梯的时候每一步的规律是「从第 N 层走一层到第 N-1 层」。这个规律就是递推公式。在代码里递推公式就是把「大问题」拆成「规模更小的同类问题」。用数学里的数学归纳法来理解就特别直观数学归纳法先证明 N1 成立再证明「如果 N 成立则 N1 也成立」。递归先写好 N1 时直接返回结果出口再写好「N 可以拆成 N-1 的结果再算一步」递推公式。二、第一个例子阶乘 —— 手把手拆解递归的执行过程什么是阶乘阶乘的数学定义5! 5 × 4 × 3 × 2 × 1 1201! 1这就是「出口」N! N × (N-1)!这就是「递推公式」写成递归代码#includestdio.hintfact(intn){if(n0)// ← 递归出口0! 1{return1;}else// ← 递推公式n! n × (n-1)!{returnn*fact(n-1);}}intmain(){intn0;scanf(%d,n);intretfact(n);printf(%d\n,ret);return0;}这个代码到底是怎么跑的假设你输入5我们一步一步追踪fact(5)的执行fact(5) 开始执行 n 5不是 0走到 else 要算 5 * fact(4) 这时候 fact(5) 暂停等 fact(4) 的结果回来—— fact(4) 开始执行 n 4不是 0走到 else 要算 4 * fact(3) 这时候 fact(4) 暂停等 fact(3) 的结果回来—— fact(3) 开始执行 n 3不是 0走到 else 要算 3 * fact(2) fact(2) 开始执行 n 2不是 0走到 else 要算 2 * fact(1) fact(1) 开始执行 n 1不是 0走到 else 要算 1 * fact(0) fact(0) 开始执行 n 0命中return 1 ← 触底了 1 * 1 1fact(1) 1 ✓ 2 * 1 2fact(2) 2 ✓ 3 * 2 6fact(3) 6 ✓ 4 * 6 24fact(4) 24 ✓ 5 * 24 120fact(5) 120 ✓关键理解递归分为两个阶段——递推阶段层层深入将问题规模逐级缩小和回归阶段到达基准情形后逐层返回结果。每一个fact(n)都暂停等待fact(n-1)的返回值直到fact(0)到达递归出口然后从最深层逐级将结果带回上层。这个过程就像你去传达室取快递——你让室友帮你去拿室友让隔壁帮他去拿隔壁让他女朋友帮他去拿……一层一层传递。最后女朋友拿到了一层一层往回递最终传到你的手里。⚠️提醒很多兄弟伙看递归代码的时候觉得「好短好简洁」但脑子里模拟不出来是怎么跑的。建议你用上面的「缩进法」手写一遍 fact(3) 的执行过程写完你就彻底理解了。关键点每一次调用都暂停自己等子问题返回结果拿到结果再继续算。三、第二个例子递归求和 —— 巩固理解问题计算 1 2 3 … N 的和按照递归的思路出口N 1 时和就是 1递推公式1 到 N 的和 N 1 到 N-1 的和intsum_n(intn){if(n1)// 出口{return1;}returnnsum_n(n-1);// 递推公式}intmain(){intretsum_n(10);printf(%d\n,ret);// 输出: 55return0;}执行过程以sum_n(3)为例sum_n(3) → 3 sum_n(2) sum_n(2) → 2 sum_n(1) sum_n(1) → 1出口 sum_n(2) ← 2 1 3 sum_n(3) ← 3 3 6什么时候用递归什么时候用循环同样的求和用循环写是这样的intsum0;for(inti1;in;i){sumi;}两者都能实现有什么区别递归循环代码长度短简洁稍长可读性接近数学定义思路清晰需要手动维护循环变量性能每次调用消耗栈空间不消耗额外空间适用场景问题本身有「自相似」结构大多数常规遍历初学阶段用哪个如果问题能清晰定义递归出口和递推公式递归代码更简洁、可读性更高。但如果数据规模很大比如 N 100000递归会导致栈溢出此时用迭代循环更安全。四、第三个例子顺序打印整数的每一位问题描述输入一个整数按从高位到低位的顺序打印出每一位数字中间用空格隔开。比如输入1234→ 输出1 2 3 4输入520→ 输出5 2 0这个题用循环怎么做你可以先算出这个数有多少位然后从最高位开始除。但代码会比较啰嗦。用递归就极其优雅voidprint(intn){if(n9)// 出口只剩一位数时直接打印{print(n/10);// 递推先打印前面的高位}printf(%d ,n%10);// 然后打印当前的最低位}为什么这个递归能实现「顺序打印」以print(1234)为例——print(1234) n 9所以调用 print(1234 / 10) print(123) print(123) n 9所以调用 print(123 / 10) print(12) print(12) n 9所以调用 print(12 / 10) print(1) print(1) n 不大于 9跳过 if printf(%d , 1 % 10) → 输出 1 ← 最高位最先 回到 print(12) printf(%d , 12 % 10) → 输出 2 回到 print(123) printf(%d , 123 % 10) → 输出 3 回到 print(1234) printf(%d , 1234 % 10) → 输出 4 最终输出1 2 3 4这个例子的精妙之处把printf写在递归调用之后。先在递推阶段深入到最高位然后在回归阶段依次打印。利用了「回归阶段从深层往浅层返回」的特性恰好实现了从高位到低位的顺序输出。⚠️提醒如果把printf写在递归调用之前输出结果就会反转——变成4 3 2 1。这是一个非常重要的认知递归调用语句之前的代码在递推阶段执行之后的代码在回归阶段执行。理解这个执行时序是掌握递归高级用法的关键。五、第四个例子斐波那契数列 —— 递归的甜蜜陷阱什么是斐波那契数列这个数列长这样1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …规律很简单从第三项开始每一项都是前两项的和。第 1 项 1第 2 项 1第 3 项 1 1 2第 4 项 1 2 3第 5 项 2 3 5以此类推……用递归写三行搞定intfib(intn){if(n2)// 出口前两项都是 1return1;elsereturnfib(n-1)fib(n-2);// 递推公式}intmain(){intretfib(5);printf(%d\n,ret);// 输出: 5return0;}看起来非常漂亮代码简洁、逻辑清晰、完美契合数学定义。但是——这个递归有一个大坑 ⚠️我们来数一下算fib(5)的时候fib函数一共被调用了多少次fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) ← 算过了 │ │ └── fib(1) ← 算过了 │ └── fib(2) ← 又算了一遍 └── fib(3) ← 又算了一遍整个 fib(3) ├── fib(2) ← 又又又算了一遍 └── fib(1) ← 又又又算了一遍fib(2)被算了 3 次而且这仅仅是n5。如果n50你会调用上亿次等半天都算不出来。这就是斐波那契递归的致命缺陷——大量重复计算。时间复杂度为 O(2ⁿ)指数级增长。当 n50 时调用次数可达数十亿量级。更好的做法用循环intfib(intn){if(n2)return1;inta1,b1,c0;for(inti3;in;i){cab;// 当前项 前两项之和ab;// 更新a 变成原来的 bbc;// 更新b 变成新算出来的 c}returnc;}这个迭代版本只需计算 n-2 次时间复杂度 O(n)性能远优于递归方案。⚠️提醒斐波那契数列给了我们一个重要教训——能用递归描述的问题不一定适合用递归求解。递归写法代码简洁但如果递推公式中同一子问题被重复计算就应当考虑用迭代替代或者引入「记忆化搜索」Memoization优化——把已经算过的结果缓存起来避免重复计算。这是校招面试中的高频考点。六、递归的「黑暗面」栈溢出Stack Overflow讲完上面四个例子你可能会有一个疑问递归一层一层往里钻会不会钻太深了出事会。这就是栈溢出。之前调试那篇文章里我们简单提过「栈区」——程序里的函数调用信息都存在栈区。每次调用一个函数栈区就会用掉一小块空间来记录「这函数是谁调用的、参数是多少、返回到哪里去」。这叫一个「栈帧」。递归每调用一次自己就多一个栈帧。调得越深栈用得越多。而栈区的大小是有限制的一般几 MB 到十几 MB。如果你忘了写递归出口或者递归层数太多栈区就会被撑爆程序直接崩溃。这个崩溃就叫「Stack Overflow」没错就是你查资料用的那个程序员网站的名字由来。但这个问题不难解决——只要递归出口写得对并且递归深度可控比如 N 不超过几千就不会栈溢出。七、递归设计方法论写递归代码的「套路」学了这么多例子我们总结出一套写递归代码的通用步骤第一步找出口问自己「这个问题最小最简单的情况是什么直接能算出答案吗」阶乘n 0 时答案是 1求和n 1 时答案是 1打印整数n 只有一位数时直接打印斐波那契n ≤ 2 时答案是 1如果找不到出口你就写不出递归。先找出口第二步找递推关系问自己「大的问题能不能用更小的小问题来表示」N! N × (N-1)!sum(N) N sum(N-1)print(1234) print(123) printf(“4”)fib(N) fib(N-1) fib(N-2)第三步检查会不会重复计算如果递推关系中同一个子问题被多次计算考虑用循环替代或者用「记忆化」把算过的结果存起来下次直接用。第四步验证会不会栈溢出估算递归深度。如果输入的最大值会导致递归层数超过几千改用循环。八、经典面试题精讲 递归是校招笔试和面试的必考内容。下面两道题但凡面 C 语言岗位十有八九会碰到。面试题一青蛙跳台阶问题题目描述一只青蛙一次可以跳上 1 级台阶也可以跳上 2 级台阶。求该青蛙跳上一个 n 级台阶总共有多少种跳法。这是剑指 Offer 和 LeetCode 上的经典原题面试中出现频率极高。思路分析想象青蛙站在第 n 级台阶上倒推它是怎么上来的——如果最后一步跳了 1 级那之前它在第 n-1 级有f(n-1)种跳法如果最后一步跳了 2 级那之前它在第 n-2 级有f(n-2)种跳法所以f(n) f(n-1) f(n-2)这不就是斐波那契数列吗区别在于初始值不同n 1 时只有 1 种跳法跳 1 级n 2 时有 2 种跳法两次 1 级 / 一次 2 级intjumpFloor(intn){if(n1)// 出口1 级台阶1 种跳法return1;if(n2)// 出口2 级台阶2 种跳法return2;returnjumpFloor(n-1)jumpFloor(n-2);// 递推公式}面试官追问「递归有大量重复计算能优化吗」这就是考察你知不知道迭代优化。用滚动变量代替递归O(n) 时间 O(1) 空间intjumpFloor(intn){if(n2)returnn;inta1,b2,c0;for(inti3;in;i){cab;ab;bc;}returnc;}面试技巧先给出递归解法展示思维过程再主动提出迭代优化展示工程意识——面试官要的就是这个节奏。面试题二汉诺塔Tower of Hanoi题目描述有三根柱子 A、B、C。A 柱上有 n 个盘子盘子从下到上按大小递减叠放。要求将所有盘子从 A 柱移动到 C 柱移动过程中遵守以下规则每次只能移动一个盘子大盘子不能放在小盘子上面打印出每一步的移动过程。汉诺塔是递归思想的标志性问题几乎所有算法教材都会讲到。思路分析把 n 个盘子从 A 移到 C怎么利用递归先把上面 n-1 个盘子从 A 移到 B借助 C 作为中转—— 这是一个规模为 n-1 的子问题把最底下那个最大的盘子从 A 直接移到 C—— 一步搞定再把 B 上的 n-1 个盘子从 B 移到 C借助 A 作为中转—— 又是一个规模为 n-1 的子问题递归出口n 1 时直接移动。#includestdio.h// n: 盘子数量, from: 起始柱, to: 目标柱, aux: 辅助柱voidhanoi(intn,charfrom,charto,charaux){if(n1){printf(将盘子 1 从 %c 移到 %c\n,from,to);return;}hanoi(n-1,from,aux,to);// 上面 n-1 个移到辅助柱printf(将盘子 %d 从 %c 移到 %c\n,n,from,to);// 最底下盘子hanoi(n-1,aux,to,from);// n-1 个从辅助柱移到目标柱}intmain(){intn3;hanoi(n,A,C,B);return0;}以 n3 为例输出如下将盘子 1 从 A 移到 C 将盘子 2 从 A 移到 B 将盘子 1 从 C 移到 B 将盘子 3 从 A 移到 C 将盘子 1 从 B 移到 A 将盘子 2 从 B 移到 C 将盘子 1 从 A 移到 C共 2³ - 1 7 步。n 个盘子需要 2ⁿ - 1 步时间复杂度 O(2ⁿ)。面试技巧汉诺塔的核心是「把大问题分解为两个子问题 一步操作」这个分治思想是递归的本质。面试时要能清晰地描述「三步走」策略证明你理解了递归的问题分解能力。 本节知识点速查知识点一句话记住递归定义函数在执行过程中调用自身递归出口Base Case问题规模缩小到可直接求解的基准情形没有出口 无限递归递推公式Recurrence将规模为 N 的问题分解为规模更小的同类子问题执行过程递推阶段Forward逐层深入 → 回归阶段Backward逐层返回阶乘fact(n) n × fact(n-1)出口n0返回 1求和sum(n) n sum(n-1)出口n1返回 1顺序打印递推阶段print(n/10)深入高位回归阶段printf(n%10)输出斐波那契递归写法 O(2ⁿ) 重复计算严重迭代优化到 O(n)栈溢出Stack Overflow递归深度过大时栈空间耗尽导致程序崩溃递归 vs 迭代递归代码简洁、契合数学定义迭代性能更高、不消耗栈空间汉诺塔分治思想两个 n-1 子问题 一步直接操作青蛙跳台阶斐波那契变体面试高频先递归再迭代优化写在最后实话跟你说 ——第一次学递归没几个人能立刻完全掌握。函数调用自身这种思维方式属于「自引用」逻辑和我们日常的线性思维习惯不同。但只要把上面的四个基础例子和两道面试题每个都动手推演一遍执行过程你的大脑就会慢慢建立起递归直觉。递归学透之后你会发现很多问题——比如树的遍历、图的搜索、分治算法——都离不开它。某种意义上递归是算法思维的分水岭。把这个技能补起以后刷 LeetCode、冲面试底气都不一样了。
