递归：自己调用自己

预计学习时长：约 2 小时（仅 L1 主线）· 运行环境：VS2026 / gcc / clang 均可

🎯 学习目标

学完本讲，你将能够：

说清"递归就是函数自己调用自己"，并解释递归的两个必要条件
用"大事化小"的思路把阶乘、按位打印写成递归函数
在纸上画出 Fact(4)、Print(1234) 的展开与回归过程
解释栈帧与栈溢出的关系，说清递归的运行时开销从哪来
判断一个问题该用递归还是迭代，并亲手测出递归斐波那契的冗余次数

🔗 先修知识

第 8 讲：函数：递归建立在函数调用、return 之上
第 6 讲：循环：迭代版本就是循环实现
第 4 讲：运算符详解：% 10 与 / 10 是取位的关键

先修自检（三问）

1234 % 10 和 1234 / 10 分别得到什么？
函数里执行 return 后，后面的语句还执行吗？
形参和实参是什么关系？

一、什么是递归

一句话：递归就是函数自己调用自己。

史上最简单的递归：

🧩 示意片段 · 会立刻栈溢出，不要单独运行

#include <stdio.h>

int main()
{
    printf("hehe\n");
    main();               // main 里又调用 main
    return 0;
}

这段代码不解决问题，只演示"自己调自己"的形式。它会一直打印 hehe 直到**栈溢出（Stack overflow）**崩溃——原因本讲第四节解释。

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

递归是一种解决问题的方法：

把一个大型复杂问题，层层转化为一个与原问题相似、但规模更小的子问题来求解；直到子问题小到不能再拆，递归就结束。

"递"是递推（一层层往下送），"归"是回归（到底了再一层层返回）。这两个字后面会反复体会。

1.2 递归的两个必要条件

写递归时必须同时满足两条，缺一条就是死递归：

#	条件	含义
1	存在限制条件	满足它时，递归不再继续（叫"递归出口"）
2	每次调用都更接近这个限制条件	参数必须朝出口方向变化

下面用两个例子体会它们。

二、举例 1：求 n 的阶乘

定义：一个正整数的阶乘是所有小于等于它的正整数之积，记作 n!，并且规定 0! = 1。

text

5! = 5 * 4 * 3 * 2 * 1
4! = 4 * 3 * 2 * 1
所以 5! = 5 * 4!

看出关键了吗——n! 可以用 (n-1)! 来表示：

text

n! = n * (n-1)!

写成完整的递归公式：

text

Fact(n) = 1,            n == 0     ← 出口
Fact(n) = n * Fact(n-1), n > 0     ← 递推

Fact(n) 和 Fact(n-1) 是同一个问题、更小的规模，正是递归的标准形态。

📄 fact.c · ✅ 完整程序（可直接复制编译）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int Fact(int n)
{
    if (n == 0)
        return 1;                  // 条件 1：出口
    else
        return n * Fact(n - 1);    // 条件 2：n-1 比 n 更接近 0
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", Fact(n));
    return 0;
}

输入 5，输出 120。

2.1 画图推演：递与归

Fact(4) 在内存里怎么走的？先看展开（递），再看返回（归）：

text

展开（递）
Fact(4)
 └─ 4 * Fact(3)
          └─ 3 * Fact(2)
                   └─ 2 * Fact(1)
                            └─ 1 * Fact(0)
                                     └─ return 1   ← 触底

回归（归）
Fact(0) 返回 1
Fact(1) = 1 * 1        = 1
Fact(2) = 2 * 1        = 2
Fact(3) = 3 * 2        = 6
Fact(4) = 4 * 6        = 24   ← 最终结果

如果没有 if (n == 0) return 1; 这四行会怎样？ Fact(0) 会继续调 Fact(-1)、Fact(-2)……永远触不到底，栈帧一路堆积直到溢出崩溃。

📘 提高（L2）：把出口写错方向

if (n == 0) 这个出口对 Fact(-1) 是无效的——传入负数会直接跳过出口一路递归到栈溢出。更稳的写法是把出口条件写成范围：if (n <= 0) return 1;。写递归时顺手想一句"万一传进来的是我预料之外的值呢"。

三、举例 2：顺序打印一个整数的每一位

需求：输入 1234，按顺序打印 1 2 3 4；输入 520，打印 5 2 0。

3.1 先看看只用循环会怎样

取每一位靠 % 10 和 / 10：

text

1234 % 10 = 4      1234 / 10 = 123
 123 % 10 = 3        123 / 10 = 12
  12 % 10 = 2         12 / 10 = 1
   1 % 10 = 1

能拿到每一位，但顺序是倒的（先拿到 4，最后才拿到 1）。要正序输出，循环写法得先把数字存进数组或字符串，比较麻烦。

3.2 换个视角：最低位最容易拿到，那就先处理高位

关键灵感：一个数的最低位是最容易得到的（% 10）。既然 4 最好拿，那就把"打印前面的 123"当成一个更小的同类问题，先解决它，最后再打印 4：

text

Print(1234) = Print(1234/10) + 打印(1234%10)
            = Print(123)     + 打印 4

继续拆：

text

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

拆到 Print(1)——它只有一位，直接打印就行，递归结束。

📄 print_digits.c · ✅ 完整程序（可直接复制编译）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void Print(int n)
{
    if (n > 9)                 // 出口条件：不是一位数才继续拆
    {
        Print(n / 10);         // 先打印高位
    }
    printf("%d ", n % 10);     // 再打印自己的最低位
}

int main()
{
    int m = 0;
    scanf("%d", &m);
    Print(m);
    printf("\n");
    return 0;
}

输入 1234 输出 1 2 3 4；输入 520 输出 5 2 0。

3.3 推演过程

text

Print(1234)  n>9 → 先调 Print(123)
  Print(123)  n>9 → 先调 Print(12)
    Print(12)  n>9 → 先调 Print(1)
      Print(1)  不大于 9，跳过递归
                打印 1%10 = 1
    回来打印 12%10 = 2
  回来打印 123%10 = 3
回来打印 1234%10 = 4

顺序为什么天然就正过来了：printf 写在递归调用之后。递归一路走到最深（最高位那一位），触底后从最深层往回打印，所以高位先出、低位后出。

💡 这行代码位置的区别，就是本讲最重要的一个手感练习：
Print(n/10); 在前、printf 在后 → 正序打印
printf 在前、Print(n/10); 在后 → 逆序打印
动手改一下试试，改完就懂了。

四、递归与迭代

递归是一种很好的技巧，但和所有技巧一样可能被误用。

4.1 递归的开销：栈帧

每次函数调用，都要在内存的栈区申请一块空间，保存这次调用期间的局部变量、参数、返回地址等，这块空间叫运行时堆栈或函数栈帧。

函数不返回，它占的栈帧就一直被占用；
递归的每一层都要开一个属于自己的栈帧；
直到递归不再展开、开始回归，这些栈帧才逐层释放。

所以递归层次太深，就会浪费大量栈帧空间，甚至引起栈溢出。

🧩 演示栈溢出 · 故意写坏，运行会崩溃（VS 弹"Stack overflow"，命令行下退出码 0xC00000FD）

#include <stdio.h>

int Fact(int n)
{
    return n * Fact(n - 1);   // 没有出口！条件 1 缺失
}

int main()
{
    printf("%d\n", Fact(5));
    return 0;
}

📜 标准卡（L2 选读）：栈溢出与递归深度

C 标准：C11 §5.2.1p5 规定实现至少要支持 127 层块嵌套、256 个块作用域标识符等最小限制；但递归深度本身标准无法规定——它取决于运行时可用的栈空间。超出限制或栈耗尽时，按 §4p4 属于不要求诊断的行为（🔴 未定义 / 🟡 实现定义）。
gcc：Windows 下默认栈 8 MB（可用 -Wl,--stack,字节数 调整），超了崩溃退出码是 0xC00000FD（STATUS_STACK_OVERFLOW）；Linux/macOS 下默认栈 8 MB（ulimit -s 可查），超了报 Segmentation fault。
MSVC：默认栈 1 MB（项目属性 → 链接器 → 系统 → 堆栈大小可改），超了运行时弹"Stack overflow"，调试器里同样是 0xC00000FD。
结论：能跑多深取决于栈大小和每层栈帧大小，不要靠调大栈来解决递归太深，改用迭代才是正解。

4.2 阶乘：迭代版本

不用递归，用循环一样能算：

📄 fact_iter.c · ✅ 完整程序（可直接复制编译）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", Fact(n));
    return 0;
}

输入 5 同样输出 120，但效率比递归好得多——一次循环，没有反复建栈退栈。

4.3 怎么选

情况	选择
问题本身是循环式的（累加、累乘、遍历数组）	迭代，效率更高
问题天然有自相似结构（树、图、分治、回溯）	递归，代码清晰得多
复杂到难以用循环写出来	递归——它的简洁性足以补偿运行时开销

事实：很多问题是"用递归解释更清晰"，但"用迭代实现更高效"。两者不是对立的，先想递归理清思路，再决定要不要换成迭代。

五、举例 3：斐波那契数——递归的反面教材

斐波那契数列就是用递归定义的：

text

F(1) = 1, F(2) = 1
F(n) = F(n-1) + F(n-2)    (n > 2)
数列：1 1 2 3 5 8 13 21 34 55 ...

看到公式很容易顺手写成递归：

📄 fib_rec.c · ✅ 完整程序（可直接复制编译；n 别输太大，会很慢）

#define _CRT_SECURE_NO_WARNINGS
#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);
    printf("%d\n", Fib(n));
    return 0;
}

n 输入 50，要等很久很久——这就是递归低效的极端例子。为什么？

5.1 冗余计算

把 Fib(5) 展开成调用树：

text

                    Fib(5)
                 /           \
            Fib(4)            Fib(3)
           /      \           /     \
       Fib(3)    Fib(2)    Fib(2)  Fib(1)
       /   \
   Fib(2) Fib(1)

Fib(3) 被算了 2 次，Fib(2) 被算了 3 次。递归越深，重复越多。用计数器实测一下：

📄 fib_count.c · ✅ 完整程序（可直接复制编译）

#define _CRT_SECURE_NO_WARNINGS
#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);
    printf("%d\n", Fib(n));
    printf("\ncount = %d\n", count);
    return 0;
}

输入 40，实测输出：

text

102334155

count = 39088169

计算第 40 个斐波那契数时，第 3 个数被重复计算了 39088169 次。 所以斐波那契用递归非常不明智，必须换迭代。

5.2 迭代版本：从前往后算

前两个数相加得到第三个数，那就从小到大一路推上去：

📄 fib_iter.c · ✅ 完整程序（可直接复制编译）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int Fib(int n)
{
    int a = 1;      // F(1)
    int b = 1;      // F(2)
    int c = 1;      // 结果；n<=2 时直接返回 1
    while (n > 2)
    {
        c = a + b;  // 新的斐波那契数
        a = b;      // 窗口往后滑一格
        b = c;
        n--;
    }
    return c;
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", Fib(n));
    return 0;
}

输入 40 立刻得到 102334155，效率比递归高出一大截。

⚠️ 注意 n <= 2 时 c 初值必须是 1，否则返回 0 就错了。这是这类题最常见的边界 bug。

递归虽好，但不要迷恋它，适可而止。 递归真正大放异彩的地方是树/图遍历、分治算法、回溯算法——等学到第 21、22 讲数据结构和第 19 讲扫雷时你会反复遇到它。

⚠️ 常见坑与报错（本讲汇总）

你看到的现象	原因	修法
程序崩溃 / Stack overflow / 段错误	忘写递归出口，或参数没朝出口变化	检查两个必要条件：有出口吗？每次更接近吗？
递归层数一深就崩	每层都要一个栈帧，栈空间有限（VS 默认 1 MB）	改用迭代；或重新设计问题规模
传入负数后崩溃	出口写成 `n == 0`，负数跳过它	出口写成范围：`if (n <= 0)`
打印顺序反了	`printf` 和递归调用的先后写颠倒了	想正序：先递归再打印；想逆序：先打印再递归
算 Fib(40) 卡住不动	递归树里大量重复计算	换迭代版本，或记住已算过的值
`Fib(1)`、`Fib(2)` 返回 0	迭代版本 c 初值写成 0	三个变量初值都设为 1
递归结果对但很慢	递归本身有建栈开销	层次不深可接受；深就改迭代

🛠️ 动手练习

规则：先独立做，卡住了再依次展开提示，不要一上来就看答案。

📊 本讲网页练习进度0 / 5（0%）

进度自动保存在本浏览器；编程题不计数，请在编辑器中完成。

练习 1 · ⭐ 基础 · 选择判断

知识点：递归的必要条件

题干：关于递归，下列说法正确的是？（多选）

练习 2 · ⭐ 基础 · 读输出

知识点：递归的展开与回归

题干：写出输出：

📄 ex2.c · ✅ 完整程序

#include <stdio.h>

void f(int n)
{
    if (n > 0)
    {
        f(n - 1);
        printf("%d ", n);
    }
}

int main()
{
    f(3);
    printf("\n");
    return 0;
}

请写出输出：

空①

练习 3 · ⭐ 基础 · 读输出

知识点：递归与逆序

题干：写出输出：

📄 ex3.c · ✅ 完整程序

#include <stdio.h>

void g(int n)
{
    if (n > 0)
    {
        printf("%d ", n);
        g(n - 1);
    }
}

int main()
{
    g(3);
    printf("\n");
    return 0;
}

请写出输出：

空①

练习 4 · ⭐ 基础 · 程序填空

知识点：递归出口

题干：补全求 n 的阶乘的递归函数（两个空）：

🧩 待补全片段

int Fact(int n)
{
    if (______)          // 第一空：出口
        return ______;   // 第二空：出口返回值
    else
        return n * Fact(n - 1);
}

第一空填条件（不写 if 和括号，只填括号内内容），第二空填返回值：

空①空②

练习 5 · ⭐ 基础 · 找错改错

知识点：递归不收敛

题干：下面这段代码会栈溢出，请填出修正后的出口条件：

🧩 待改错片段

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

提示：调用 Fib(1) 时会算 Fib(0)、Fib(-1)……请填出正确的出口条件（不写 if 和括号）：

空①

练习 6 · ⭐⭐ 提高 · 写小程序

知识点：递归取位

🛠 动手编程题 · 请在 VS2026（或你的编辑器）中完成

写一个递归函数 void PrintReverse(int n)，逆序打印一个正整数的每一位（输入 1234，输出 4321）。

✅ 过关标准：PrintReverse(1234) 输出 4321；PrintReverse(520) 输出 025。

网页内无法练习写代码，亲手敲、亲手编译才能真正学会。下方按顺序展开思路 → 步骤 → 答案。

💡 提示 1（思路）

本讲的 Print 是"先递归、后打印"得到正序；逆序只要把两行调换位置。

🧭 提示 2（步骤）

先 printf("%d", n % 10); 打印最低位
再 if (n > 9) PrintReverse(n / 10);
注意：出口判断要在打印之后

🔑 参考答案与解释

#include <stdio.h>

void PrintReverse(int n)
{
    printf("%d", n % 10);      // 先打印最低位
    if (n > 9)
        PrintReverse(n / 10);  // 再处理剩下的高位
}

int main()
{
    PrintReverse(1234);        // 4321
    printf("\n");
    PrintReverse(520);         // 025
    printf("\n");
    return 0;
}

要点：printf 在前就是逆序输出。第二组结果 025 说明它按位打印、不关心数值大小——末尾的 0 也会被打印出来，这是"打印每一位"和"打印一个数"的区别。

练习 7 · ⭐⭐ 提高 · 写小程序

知识点：递归求和

🛠 动手编程题 · 请在 VS2026（或你的编辑器）中完成

写一个递归函数 `int sum(int n)`，返回 `1 + 2 + 3 + ... + n`。在 main 中打印 `sum(100)`。

✅ 过关标准：输出 5050；再测 sum(1) 得 1、sum(0) 得 0。

网页内无法练习写代码，亲手敲、亲手编译才能真正学会。下方按顺序展开思路 → 步骤 → 答案。

💡 提示 1（思路）

sum(n) = n + sum(n-1)，出口是 n 为 0 时返回 0。

🧭 提示 2（步骤）

出口：if (n <= 0) return 0;
递推：return n + sum(n - 1);
main 里 printf("%d\n", sum(100));

🔑 参考答案与解释

#include <stdio.h>

int sum(int n)
{
    if (n <= 0)
        return 0;
    return n + sum(n - 1);
}

int main()
{
    printf("%d\n", sum(100));
    printf("%d\n", sum(1));
    printf("%d\n", sum(0));
    return 0;
}

注意：阶乘的出口返回 1（乘法单位元），求和的出口返回 0（加法单位元）——出口值取决于运算是乘还是加，写反了结果全错。另外 sum(100000) 一定会栈溢出，这种累加本来就该用循环。

练习 8 · ⭐⭐⭐ 挑战 · 写小程序

知识点：递归的经典应用——汉诺塔

🛠 动手编程题 · 请在 VS2026（或你的编辑器）中完成

三根柱子 A、B、C，初始时 n 个盘子从小到大叠在 A 上。每次只能移动一个盘子，且大盘不能压小盘。写递归函数 `Hanoi(int n, char src, char dest, char aux)` 打印每一步移动（格式 `A -> C`）。

✅ 过关标准：Hanoi(3, 'A', 'C', 'B') 打印 7 行，依次为 A -> C、A -> B、C -> B、A -> C、B -> A、B -> C、A -> C。

网页内无法练习写代码，亲手敲、亲手编译才能真正学会。下方按顺序展开思路 → 步骤 → 答案。

💡 提示 1（思路）

要把 n 个盘子从 src 挪到 dest，只需想三步：把上面 n-1 个先挪去 aux（借助 dest）→ 把最大的那个从 src 挪到 dest → 把 aux 上那 n-1 个挪到 dest（借助 src）。

🧭 提示 2（步骤）

出口：n == 1 时直接 printf("%c -> %c\n", src, dest);
Hanoi(n-1, src, aux, dest);
打印最大盘 src -> dest
Hanoi(n-1, aux, dest, src);

🔑 参考答案与解释

#include <stdio.h>

// 把 n 个盘子从 src 移到 dest，aux 是辅助柱
void Hanoi(int n, char src, char dest, char aux)
{
    if (n == 1)
    {
        printf("%c -> %c\n", src, dest);
    }
    else
    {
        Hanoi(n - 1, src, aux, dest);      // 上面 n-1 个先让路
        printf("%c -> %c\n", src, dest);   // 最大盘直接到位
        Hanoi(n - 1, aux, dest, src);      // n-1 个搬回来
    }
}

int main()
{
    Hanoi(3, 'A', 'C', 'B');
    return 0;
}
/* 输出：
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
*/

为什么是递归：移 n 个的问题被拆成两个"移 n-1 个"的同款子问题，只是三根柱子的角色换了个位置——这就是"与原问题相似、规模更小"。n 个盘子最少需要 2ⁿ − 1 步，n=3 正好 7 步。这类"换个参数就是同一个问题"的结构，用循环写会非常痛苦，用递归三行搞定。

📝 小结与自测

本讲主线：递归 = 函数自己调用自己，思路是把大事化成同类的更小的事；写递归必须满足两个条件（有出口、每次更接近出口）；printf 放在递归调用前还是后，决定输出正序还是逆序；每次调用都要一个栈帧，层次太深就是浪费甚至栈溢出；能用循环自然表达的就用迭代（阶乘、斐波那契），天然自相似的（汉诺塔、后面的树）才用递归。

自测四问：

递归的两个必要条件分别是什么？缺了会怎样？
Fact(4) 展开到最深处是第几次调用？回归时依次得到什么值？
为什么递归版 Fib(40) 慢到不可接受？迭代版为什么快？
想把一个整数按位逆序打印，代码上的改动是什么？

🔬 选学拓展（L3）

以下内容超出主线要求

适合学有余力的同学，不影响后续学习。

L3-1：青蛙跳台阶

问题：一共有 n 级台阶，一次可以跳 1 级或 2 级，问跳到第 n 级共有多少种跳法？

分析：到达第 n 级的最后一步，要么从第 n-1 级跳 1 步上来，要么从第 n-2 级跳 2 步上来，两类互不重叠，所以

text

f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

看出熟悉的结构了吗——这就是斐波那契数列，只是起始值不同。

📄 frog.c · ✅ 完整程序（可直接复制编译）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", Frog(n));
    return 0;
}

输入 30 输出 1346269。n 稍大就会明显变慢，原因和斐波那契完全一样——递归树里有大量重复计算。请用本讲学的迭代方式改写它，作为练习。

L3-2：用"记忆化"救回递归

既想要递归的清晰，又想去掉重复计算，可以把算过的结果存起来：

📄 fib_memo.c · ✅ 完整程序（可直接复制编译）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int memo[100] = {0};          // 0 表示还没算过

int Fib(int n)
{
    if (n <= 2)
        return 1;
    if (memo[n] != 0)
        return memo[n];       // 算过就直接给答案
    memo[n] = Fib(n - 1) + Fib(n - 2);
    return memo[n];
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", Fib(n));
    return 0;
}

输入 40 瞬间得到 102334155。每个值只算一次，代价是一个数组存结果——这个思路叫记忆化，是第 21 讲之后学动态规划的基础。

L3-3：递归深度的现场测量

想知道自己的机器能递归多深？加个计数器：

📄 depth.c · ✅ 完整程序（可直接复制编译；会崩溃，崩溃前会打印出深度）

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

long depth = 0;

void dive(void)
{
    depth++;
    if (depth % 10000 == 0)
    {
        printf("depth = %ld\n", depth);
        fflush(stdout);        // 必须刷新，否则崩溃时缓冲区里的内容全丢
    }
    dive();                    // 没有出口，专门用来撞栈
}

int main()
{
    dive();
    return 0;
}

在本机 MinGW gcc（-O0 编译，每层栈帧极小）上实测：3 万层安然无恙，4 万层仍可，4.5 万层直接崩溃——也就是约 4 万层这个量级。VS 默认栈只有 1 MB（gcc 是 8 MB），能撑的深度明显更浅；而每层函数如果有较大的局部数组，深度会成倍下降。同一个逻辑，能递归多深由"栈大小 ÷ 每层栈帧大小"决定——这正是"不要靠递归处理超大规模数据"的实证。

⚠️ 这个程序一定会崩溃，只用来观察深度数字，不要放进正式项目。
💡 顺带学一个实用技巧：printf 的输出默认是带缓冲的，程序异常崩溃时缓冲区来不及写出，屏幕上就会一片空白。所以"想在崩溃前看到日志"必须手动 fflush(stdout)——调试崩溃类问题时特别有用。
💡 另一个坑：-Wall 下 gcc 会对这种无出口递归报 warning: infinite recursion detected。看到这条警告别忽略，它说明编译器已经看出你的递归永远回不来。

递归：自己调用自己 ​

🎯 学习目标 ​

🔗 先修知识 ​

一、什么是递归 ​

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

1.2 递归的两个必要条件 ​

二、举例 1：求 n 的阶乘 ​

2.1 画图推演：递与归 ​

三、举例 2：顺序打印一个整数的每一位 ​

3.1 先看看只用循环会怎样 ​

3.2 换个视角：最低位最容易拿到，那就先处理高位 ​

3.3 推演过程 ​

四、递归与迭代 ​

4.1 递归的开销：栈帧 ​

4.2 阶乘：迭代版本 ​

4.3 怎么选 ​

五、举例 3：斐波那契数——递归的反面教材 ​

5.1 冗余计算 ​

5.2 迭代版本：从前往后算 ​

⚠️ 常见坑与报错（本讲汇总） ​

🛠️ 动手练习 ​

练习 1 · ⭐ 基础 · 选择判断 ​

练习 2 · ⭐ 基础 · 读输出 ​

练习 3 · ⭐ 基础 · 读输出 ​

练习 4 · ⭐ 基础 · 程序填空 ​

练习 5 · ⭐ 基础 · 找错改错 ​

练习 6 · ⭐⭐ 提高 · 写小程序 ​

练习 7 · ⭐⭐ 提高 · 写小程序 ​

练习 8 · ⭐⭐⭐ 挑战 · 写小程序 ​

📝 小结与自测 ​

🔬 选学拓展（L3） ​

L3-1：青蛙跳台阶 ​

L3-2：用"记忆化"救回递归 ​

L3-3：递归深度的现场测量 ​

递归：自己调用自己

🎯 学习目标

🔗 先修知识

一、什么是递归

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

1.2 递归的两个必要条件

二、举例 1：求 n 的阶乘

2.1 画图推演：递与归

三、举例 2：顺序打印一个整数的每一位

3.1 先看看只用循环会怎样

3.2 换个视角：最低位最容易拿到，那就先处理高位

3.3 推演过程

四、递归与迭代

4.1 递归的开销：栈帧

4.2 阶乘：迭代版本

4.3 怎么选

五、举例 3：斐波那契数——递归的反面教材

5.1 冗余计算

5.2 迭代版本：从前往后算

⚠️ 常见坑与报错（本讲汇总）

🛠️ 动手练习

练习 1 · ⭐ 基础 · 选择判断

练习 2 · ⭐ 基础 · 读输出

练习 3 · ⭐ 基础 · 读输出

练习 4 · ⭐ 基础 · 程序填空

练习 5 · ⭐ 基础 · 找错改错

练习 6 · ⭐⭐ 提高 · 写小程序

练习 7 · ⭐⭐ 提高 · 写小程序

练习 8 · ⭐⭐⭐ 挑战 · 写小程序

📝 小结与自测

🔬 选学拓展（L3）

L3-1：青蛙跳台阶

L3-2：用"记忆化"救回递归

L3-3：递归深度的现场测量