写在前面：递归不是靠背模板学会的

刚开始学递归那会，我们大多数人脑子里就一个印象——"函数自己调用自己"。背几个例题、套几个公式，好像也会写了。可一到自己动手，就卡在"递到什么时候停""返回值怎么一层层传回来"这些地方，死活绕不明白。下面这篇复盘，是我把函数递归这一讲重新拆了一遍：从"为什么会有递归"讲到"两个限制条件"，再到阶乘、打印每一位、斐波那契三个例子里踩过的坑，最后聊聊递归和迭代到底怎么选。不追求把模板背下来，只求把"大事化小"这个思路真正讲透。

一、递归是什么：为什么说它是"自己调用自己"

递归是学 C 语言函数绕不开的一个话题。说白了，递归就是一种解决问题的方法，在 C 语言里，它就是函数自己调用自己。

先看一段史上最简单的递归代码：

#include <stdio.h> int main() { printf("hehe\n"); main(); // main 函数里又调用了 main 函数 return 0; }

这段代码只是用来演示递归基本形式的"反面教材"——它不是为了解决问题，最终会陷入死递归，直接栈溢出（Stack Overflow）。

为什么会栈溢出？我们先按下不表，第三节「递归与迭代」会专门讲。这里先记住一句话：递归必须得有结束条件，否则就是灾难。

1.1 递归的思想：把大事化小

递归的核心思路，就是把一个大而复杂的问题，一层层转化成一个跟原问题相似、但规模更小的子问题，直到子问题拆不动了，递归就结束了。

所以递归的思考方式，本质上就是"大事化小"。

拆开"递归"这两个字，其实特别有意思：

• 递，是递推，把问题一层层"递"下去，规模越来越小；
• 归，是回归，子问题解决之后，再一层层"归"回来。

先递后归，合起来才是递归。很多同学只记住了"递"、忽略了"归"，所以才觉得递归难。

1.2 递归的两个限制条件

写递归的时候，有两个必要条件，缺一不可：

1. 递归得有限制条件——满足这个条件时，递归就不再继续；
2. 每次递归调用之后，都要越来越接近这个限制条件。

这两条是写递归的"铁律"：第一条保证递归停得下来，第二条保证它确实会走到停的那一步。下面三个例子，我们会反复体会这两条。

二、三个经典例题：从"看得懂"到"会写"

2.1 求 n 的阶乘：一个公式引出的递归

阶乘（factorial）是啥？一个正整数的阶乘，就是所有小于等于它的正整数相乘，另外规定0 的阶乘是 1，记作n!。

题目：算 n 的阶乘（先不考虑溢出），也就是 1~n 的累积相乘。

分析思路

阶乘的公式大家都熟：n! = n × (n−1)!。举个具体的：

• 5! = 5 × 4 × 3 × 2 × 1
• 4! = 4 × 3 × 2 × 1
• 所以5! = 5 × 4!

看出门道了吗？这就把一个"求 n!"的大问题，转化成了"求 (n−1)!"的小问题——正是大事化小。当n == 0时，0 的阶乘是 1，其余都能套公式。于是递归公式长这样：

Fact(n) = 1 （n == 0 时） = n * Fact(n-1)（n > 0 时）

代码实现

假设Fact(n)就是求 n 的阶乘，那Fact(n-1)就是求 n-1 的阶乘，函数如下：

int Fact(int n) { if (n == 0) return 1; else return n * Fact(n - 1); }

完整测试代码：

#include <stdio.h> int Fact(int n) { if (n == 0) return 1; else return n * Fact(n - 1); } int main() { int n = 0; scanf("%d", &n); int ret = Fact(n); printf("%d\n", ret); return 0; }

运行结果（这里不考虑 n 太大的情况，n 太大存在溢出）：

输入：5 输出：120

画图推演

以Fact(5)为例，看"递"和"归"到底怎么走的：

【待插入图片】图1：Fact(5) 的「递」与「归」推演

实线箭头是递（向下递归调用），虚线箭头是归（逐层返回结果）。最内层的Fact(0)先返回 1，再逐层乘回去，最终得到 120。这一步看懂了，递归的"归"也就懂了。

2.2 顺序打印整数的每一位：先递归还是先打印？

题目：输入一个整数 m，按顺序打印它的每一位。比如输入1234输出1 2 3 4，输入520输出5 2 0。

分析思路

这题第一反应是：怎么拿到每一位？

• n 是一位数，每一位就是 n 自己；
• n 超过一位，就得拆。

规律很简单：1234 % 10得到 4，1234 / 10得到 123，相当于把 4 去掉了；再123 % 10得 3，再/10去 3……不断%10和/10，直到每一位都被拆出来。

但这里有个坑：这样拆出来的数字顺序是反的（先拿到 4、3、2、1）。

不过换个角度，我们反而有了灵感：一个数最低位最好拿（%10一下就出来了）。那我们写个函数Print，把Print(1234)拆成两步：

1. Print(1234/10)→ 打印 123 的每一位
2. printf(1234%10)→ 打印 4

两步做完，1234 的每一位就打印完了。以此类推：

Print(1234) ==> Print(123) + printf(4) ==> Print(12) + printf(3) ==> Print(1) + printf(2) ==> printf(1)

直到数字变成一位数，不用再拆，递归结束。

代码实现

void Print(int n) { if (n > 9) { Print(n / 10); } printf("%d ", n % 10); } int main() { int m = 0; scanf("%d", &m); Print(m); return 0; }

运行结果：

输入：1234 输出：1 2 3 4

这题的关键在于：printf写在递归调用之后，也就是先递归、后打印。最内层的Print(1)先打印，返回时再依次打印 2、3、4，顺序正好被"纠正"过来了。这个顺序，很多同学第一次都会写反。

画图推演

【待插入图片】图2：Print(1234) 顺序打印每一位的推演

三、递归与迭代：别迷恋递归

递归是个好东西，但和很多技巧一样，也容易被误用。就拿求阶乘来说，看到公式，手一滑就写成递归了。Fact函数确实能出正确结果，但递归调用是有运行时开销的：

• C 语言里每次函数调用，都要在内存的栈区申请一块空间，保存调用期间各种局部变量的值，这块空间叫运行时堆栈，也就是函数栈帧。
• 函数不返回，栈帧就一直占着。递归里每次调用都开新栈帧，直到不再递归、开始回归，才逐层释放。
• 所以递归层次太深，就会大量浪费栈帧，甚至栈溢出（Stack Overflow）。

这也正是开头那段main递归会栈溢出的根本原因：每次调用都开新栈帧、又永远不返回，栈空间很快就被耗光。

不想用递归，通常就用迭代（循环）。比如求阶乘，同样能 1~n 累积相乘：

int Fact(int n) { int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret *= i; } return ret; }

这段代码照样完成任务，而且效率比递归更好。

事实上，很多问题用递归描述更清晰，但迭代实现往往效率更高。当问题复杂到难以用迭代实现时，递归的简洁性就能补偿运行时开销。

3.1 求第 n 个斐波那契数：递归的"反面典型"

再举一个更极端的例子：算第 n 个斐波那契数。数列是1, 1, 2, 3, 5, 8, 13, ...，递推公式：

Fib(n) = 1 （n <= 2 时） = Fib(n-1) + Fib(n-2)（n > 2 时）

看到这个公式，很容易手滑写成递归：

int Fib(int n) { if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); }

测试代码：

#include <stdio.h> int Fib(int n) { if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }

当我们输入n = 50，结果要等很久很久才出来——这个时间谁都接受不了，说明递归写法非常低效。

为什么这么慢？递归会不断展开，展开过程中有大量重复计算，而且层次越深，冗余越多。写个计数器验证：

#include <stdio.h> int count = 0; int Fib(int n) { if (n == 3) count++; // 统计第 3 个斐波那契数被算了几次 if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); printf("\ncount = %d\n", count); return 0; }

输出：

输入：40 输出：102334155 count = 39088169

看到没？算第 40 个斐波那契数，光第 3 个数就被重复算了 39088169 次！全是冗余计算。所以斐波那契数，用递归是非常不明智的。

画图推演

【待插入图片】图3：Fib(5) 递归树——重复计算一目了然

图里Fib(3)被算了2 次，这才只是 n=5。n 越大，重复量会指数级膨胀。

既然递归不合适，就换迭代：从前往后、从小到大算。前 2 个数都是 1，前两个相加就是第三个：

int Fib(int n) { int a = 1; int b = 1; int c = 1; while (n > 2) { c = a + b; a = b; b = c; n--; } return c; }

迭代实现，效率高出很多。

四、总结：递归的正确打开方式

最后收个尾：

1. 递归的本质：函数自己调用自己，核心是"大事化小"，别只记"递"忘了"归"。
2. 写递归的两条铁律：① 有限制条件；② 每次调用都更接近限制条件。
3. 递归的代价：每次调用都开函数栈帧，层次太深会栈溢出，还可能有大量重复计算。
4. 递归 vs 迭代：递归简洁易读，迭代通常更高效；迭代难写时，递归的简洁能补回运行时开销。

一句话收尾：递归虽好，可别迷恋，适可而止就好。

拓展学习

下面两个经典问题都能用递归漂亮地解决，感兴趣可以研究：

• 青蛙跳台阶问题
• 汉诺塔问题