在编程世界里，有些概念让你第一次听到时会觉得"这怎么可能？"——递归就是其中之一。你写了一个函数，然后在这个函数里又调用了这个函数本身。这听起来像是一个无限循环的陷阱，但在正确的条件下，它却是一种极其优雅的解题方式。
在开始之前，先回顾一个你已经熟练掌握的背景知识：函数调用时会在内存的栈区分配一块空间（叫做栈帧），用来保存局部变量和返回地址；函数返回时这块空间才会被释放。这个机制对理解递归至关重要——因为递归就是通过不断创建栈帧来一层层推进计算的。
什么是递归？
从形式上说，递归就是在一个函数内部直接或间接地调用自身。世界上最简单的递归代码长这样：
#include <stdio.h>
int main()
{
printf("hehe\n");
main(); // main 函数中又调用了 main 函数自身
return 0;
}运行这段代码，你会看到屏幕上疯狂打印 "hehe"，然后……程序崩溃了。为什么会崩溃？因为每次调用 main 都会在栈上分配一块栈帧空间，而这块空间只有等函数返回后才能释放。main 永远不返回，栈帧越堆越多，最终撑爆了栈空间——这就是著名的栈溢出（Stack Overflow）。
所以这段代码只是为了说明"递归的形式"，它不是真正有用的递归。真正有用的递归，必须满足两个条件：
- 存在终止条件（也叫"基线条件"）：当满足这个条件时，递归不再继续；
- 每次递归调用都向终止条件靠近：参数在每次调用中逐渐变化，最终一定会触发终止条件。
这两个条件缺一不可——缺第一个会无限递归，缺第二个就算有终止条件也永远到不了。
递归的两个视角
理解递归有两种层次：
- 形式上的递归：函数调用自己——这只是语法层面；
- 思想上的递归：大事化小——把一个大问题分解成"更小的同类问题"，小到可以直接求解为止。
真正的高手写递归，靠的是第二种视角。当你看到"求 n 的阶乘"，先想"n! = n × (n-1)!"——问题规模从 n 变成了 n-1，这就是递归思想的入口。
递归的举例
递归的核心思想可以用四个字概括——大事化小。把一个大型复杂问题，层层转化为一个与原问题相似但规模更小的子问题来求解；直到子问题简单到可以直接求解，递归就结束了。
"递归"这个词包含了两个过程：
- "递"（递推）：一层层地把问题缩小，不断推进；
- "归"（回归）：从最小的子问题开始，一层层地把答案传回来。
理解了这个"递→归"的过程，你才算真正懂了递归。
举例 1：阶乘
n 的阶乘是 1 到 n 所有整数的乘积，记作 n!。特别地，0! = 1。
先看数学推导：
5! = 5 × 4 × 3 × 2 × 1
4! = 4 × 3 × 2 × 1
所以：5! = 5 × 4!
n! = n × (n-1)! （当 n > 0）
0! = 1 （当 n = 0）
关键洞察：n 的阶乘和 n-1 的阶乘是同一类问题，只是规模缩小了。 当你把问题描述成"n! = n × (n-1)!"时，递归的结构就已经呼之欲出了。
用代码表达：
#include <stdio.h>
// 递归实现阶乘
// 思考过程：Fact(n) 表示求 n 的阶乘
// - 如果 n == 0，直接返回 1（终止条件）
// - 如果 n > 0，返回 n * Fact(n-1)（大事化小）
int Fact(int n)
{
if (n == 0) // 终止条件：0! = 1
return 1; // 不再继续递归，开始"归"
else
return n * Fact(n - 1); // 递推：把 n! 转化为 n × (n-1)!
}
int main()
{
int n = 0;
scanf("%d", &n); // 输入 5
int ret = Fact(n); // 计算 5!
printf("%d\n", ret); // 输出 120
return 0;
}（注意：int 能表示的范围有限，13! 就已经超过 32 位 int 的上限了。这里不考虑 n 太大的情况，实际工程中遇到大数阶乘要考虑溢出，或者改用更大范围的类型。）
让我们用 n=5 来推演整个执行过程：
Fact(5) ← 调用 Fact(5)
= 5 * Fact(4) ← 需要等 Fact(4) 返回
Fact(4)
= 4 * Fact(3) ← 需要等 Fact(3) 返回
Fact(3)
= 3 * Fact(2)
Fact(2)
= 2 * Fact(1)
Fact(1)
= 1 * Fact(0)
Fact(0)
= 1 ← 终止！开始回归
= 1 * 1 = 1 ↑
= 2 * 1 = 2 ↑
= 3 * 2 = 6 ↑
= 4 * 6 = 24 ↑
= 5 * 24 = 120 ↑
第一阶段是"递"——从 Fact(5) 一路推到 Fact(0)，每次都在栈上开辟一个新的栈帧；第二阶段是"归"——从 Fact(0)=1 开始，一路把结果乘回来。
注意乘法是在"归"的路上发生的：5 * Fact(4) 中的乘法必须等 Fact(4) 返回后才能算。也就是说，递归调用后面的代码（这里是乘法），全部被"挂起"到了回归阶段——这是理解递归执行顺序的关键。
举例 2：顺序打印整数的每一位
输入一个整数，按顺序打印它的每一位数字。比如输入 1234，输出 1 2 3 4。
先分析非递归怎么做：1234 % 10 = 4 拿到个位，1234 / 10 = 123 去掉个位……循环下去。问题是——这样拿到的数字顺序是反的（4→3→2→1），不是我们想要的正序（1→2→3→4）。
递归能完美解决这个"顺序"问题。关键思考是这样的：
Print(1234)：
= Print(123) // ① 先打印 123 的每一位（正序）
+ printf("%d ", 1234 % 10) // ② 再打印个位数字 4
Print(123)：
= Print(12) // ① 先打印 12 的每一位
+ printf("%d ", 123 % 10) // ② 再打印 3
Print(12)：
= Print(1) // ① 先打印 1 的每一位
+ printf("%d ", 12 % 10) // ② 再打印 2
Print(1)：
= printf("%d ", 1) // 只有一位数，直接打印（终止条件！）
你会发现一个非常巧妙的现象：打印（输出）发生在"归"的阶段，而不是"递"的阶段。 这种"递的时候不做实际工作，归的时候再执行"的模式，是递归中非常常见的套路。
#include <stdio.h>
// 递归实现：顺序打印整数的每一位
// 思路：
// - 如果 n > 9（不止一位），先递归打印 n/10 的每一位
// - 然后打印 n%10（当前最低位）
// - 由于输出在递归调用之后，所以实际打印顺序是"高位先输出"
void Print(int n)
{
if (n > 9) // 不止一位数，需要继续拆分
{
Print(n / 10); // "递"：先处理高位部分
}
// "归"：递归返回后，逐个打印当前位
printf("%d ", n % 10); // 这个 printf 在每次递归回归时执行
}
int main()
{
int m = 0;
scanf("%d", &m);
Print(m); // 输入 1234，输出 "1 2 3 4"
printf("\n");
return 0;
}理解这个例子的关键是：printf 在递归调用之后。如果你是第一次接触递归，建议你在脑子里画个调用栈图，逐层推演一遍。你会惊叹于这种"先深入、再回头"的执行模式。
递归与迭代
递归看起来很优雅对吧？但它不是银弹。让我们用一个经典的"陷阱"例子来看看递归的黑暗面——斐波那契数列。
斐波那契数列的定义（同样充满了递归的味道）：
Fib(1) = 1
Fib(2) = 1
Fib(n) = Fib(n-1) + Fib(n-2) （n > 2）
看到这个公式，90% 的人第一反应都是写递归：
#include <stdio.h>
// 递归求第 n 个斐波那契数
int Fib(int n)
{
if (n <= 2) // 前两个数都是 1（终止条件）
return 1;
else
return Fib(n - 1) + Fib(n - 2); // 第 n 个 = 前两个之和
}
int main()
{
int n = 0;
scanf("%d", &n); // 试试输入 50
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}代码完全正确，逻辑无懈可击。但试试输入 50——你会发现程序卡住了，等了好久都出不来结果。为什么？因为这段递归代码的计算量是一个天文数字。
问题出在重复计算。来分析 Fib(5) 的计算过程：
Fib(5)
├── Fib(4)
│ ├── Fib(3)
│ │ ├── Fib(2)
│ │ └── Fib(1)
│ └── Fib(2)
└── Fib(3)
├── Fib(2)
└── Fib(1)
Fib(3) 被计算了 2 次，Fib(2) 被计算了 3 次。n 越大，重复计算的次数越是爆炸式增长。
我们来做个实验——统计 Fib(3) 在计算 Fib(40) 时被重复计算了多少次：
#include <stdio.h>
int count = 0; // 全局变量，统计 Fib(3) 被计算的次数
int Fib(int n)
{
if (n == 3)
count++; // 每次计算到 Fib(3) 就计数
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 40;
int ret = Fib(n);
printf("Fib(%d) = %d\n", n, ret);
printf("Fib(3) 被重复计算了 %d 次\n", count);
// 输出：Fib(3) 被重复计算了 39088169 次！
return 0;
}三千九百万次！算 Fib(40) 的过程中，光是 Fib(3) 这个相同的子问题就被算了 39088169 次。时间复杂度是 O(2^n)，指数级增长——这就是为什么 Fib(50) 能让你的电脑算到天荒地老。
正确的做法是改用迭代——从前往后算：
#include <stdio.h>
// 迭代（循环）求第 n 个斐波那契数
// 时间复杂度 O(n)，空间复杂度 O(1)
int Fib(int n)
{
int a = 1; // 第 1 个斐波那契数
int b = 1; // 第 2 个斐波那契数
int c = 1; // 用于存储最新计算结果
while (n > 2) // 从第 3 个开始循环计算
{
c = a + b; // 当前项 = 前两项之和
a = b; // a 向前移动一位
b = c; // b 向前移动一位
n--; // 计数器递减
}
return c; // 返回第 n 个数
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n); // 即使输入 50，也是秒出结果
printf("%d\n", ret);
return 0;
}这段迭代代码的时间复杂度是 O(n)，空间复杂度是 O(1)。Fib(50) 瞬间算完，跟递归版相比简直是降维打击。
递归的底层代价：函数栈帧
为什么递归会有性能问题？答案在于函数调用在内存中的机制。每次函数调用都会在栈区压入一个新的栈帧来保存局部变量、参数和返回地址。函数不返回，它的栈帧就不会释放。递归调用会不断压入新栈帧——像叠盘子一样越叠越高。
高地址（栈底）
┌──────────────┐
│ main 栈帧 │
├──────────────┤
│ Fact(5) 栈帧 │
├──────────────┤
│ Fact(4) 栈帧 │
├──────────────┤
│ Fact(3) 栈帧 │
├──────────────┤
│ Fact(2) 栈帧 │
├──────────────┤
│ Fact(1) 栈帧 │
├──────────────┤
│ Fact(0) 栈帧 │ ← 栈顶（当前正在执行）
└──────────────┘
低地址（栈顶，栈向低地址增长）
这就引出了递归的两大风险：
- 栈溢出：递归层数太深，栈空间耗尽。Linux 下默认栈大小通常是 8MB，如果每层栈帧比较大，可能几千层就溢出了；
- 性能开销：每次函数调用都有压栈、跳转、出栈的开销，加上潜在的重复计算，递归可能比等效的循环慢几个数量级。
所以如何选择递归还是迭代？当递归能让代码清晰简洁、递归深度可控时，用递归；当迭代同样清晰但效率更高时，用迭代。斐波那契就是"不要用递归"的教科书级反例。
下面再看几个递归的实际应用例子——
求字符串长度（不能用 strlen）：
#include <stdio.h>
// 递归计算字符串长度
// 思路：字符串长度 = 1（当前字符） + 剩余字符串的长度
// 终止条件：遇到 '\0'（空字符），长度为 0
int MyStrlen(const char* str)
{
if (*str == '\0') // 终止条件：字符串结束
return 0; // 空字符串长度为 0
else
return 1 + MyStrlen(str + 1); // 当前字符 + 剩余部分的长度
// ↑ str+1 是指针向后移一位，指向下一个字符
}
int main()
{
char arr[] = "Hello";
int len = MyStrlen(arr); // 递归计算
printf("字符串 \"%s\" 的长度是：%d\n", arr, len); // 输出 5
return 0;
}求 n 的 k 次方（递归版）：
#include <stdio.h>
// 递归计算 n 的 k 次方
// n^k = n * n^(k-1)，当 k == 0 时结果为 1
double Power(int n, int k)
{
if (k == 0) // 任何数的 0 次方都是 1（终止条件）
return 1.0;
else if (k > 0)
return n * Power(n, k - 1); // 正指数：n^k = n * n^(k-1)
else
return 1.0 / Power(n, -k); // 负指数：n^(-k) = 1 / n^k
}
int main()
{
int n = 2, k = 10;
printf("%d 的 %d 次方 = %.0f\n", n, k, Power(n, k)); // 1024
printf("%d 的 %d 次方 = %f\n", n, -3, Power(n, -3)); // 0.125000
return 0;
}反转字符串（递归版）：
#include <stdio.h>
#include <string.h>
// 递归反转字符串
// 思路：交换首尾字符，然后递归处理中间部分
void ReverseString(char* str, int left, int right)
{
if (left >= right) // 终止条件：区间为空或只有一个字符
return;
// 交换首尾字符
char temp = str[left];
str[left] = str[right];
str[right] = temp;
// 递归处理中间部分
ReverseString(str, left + 1, right - 1);
}
int main()
{
char str[] = "HelloWorld";
printf("原字符串：%s\n", str); // HelloWorld
ReverseString(str, 0, strlen(str) - 1);
printf("反转后：%s\n", str); // dlroWolleH
return 0;
}写递归时有几个容易踩的坑要特别注意：
忘记写终止条件——这是最致命的，会导致无限递归直到栈溢出。每次写递归，先写终止条件。
终止条件逻辑有误——比如阶乘的终止条件应该是 n == 0 而不是 n == 1。如果写成 n == 1，调用 Fact(0) 就会无限递归。
递归深度过大导致栈溢出——如果递归层次可能超过几千层，就该考虑用迭代。C 语言标准不保证尾递归优化，不要依赖编译器帮你消除栈帧。
递归函数中慎用静态局部变量——static 变量在所有递归层共享，第二次调用这个函数时，静态变量还保留着上次的值，结果完全不可预测。
经典递归问题（一）：汉诺塔
汉诺塔是递归的"图腾级"问题，几乎每一本讲递归的教材都会讲它。问题描述是这样的：
有三根柱子 A、B、C，A 柱上从上到下叠着 n 个大小不一的圆盘（小的在上、大的在下）。要求把所有圆盘从 A 移到 C，每次只能移动一个圆盘，且任何时候大圆盘都不能压在小圆盘上面。B 柱作为辅助。问：怎么移动？最少需要移动多少次？
先思考 n=1：直接把 A 上的圆盘移到 C，一步搞定。
n=2：小盘 A→B，大盘 A→C，小盘 B→C，共 3 步。
n=3：可以这样想——先想办法把上面 2 个盘从 A 移到 B（借助 C），再把最大的盘从 A 移到 C，最后把 B 上的 2 个盘移到 C（借助 A）。总共 7 步。
你有没有发现规律？把 n 个盘从 A 移到 C 的问题，被拆成了三步：
- 把 n-1 个盘从 A 移到 B（借助 C）——这是一个规模为 n-1 的同类问题！
- 把第 n 个（最大的）盘从 A 移到 C——一步，直接做；
- 把 n-1 个盘从 B 移到 C（借助 A）——又是一个规模为 n-1 的同类问题！
这就是递归思想的完美体现：整个问题的结构，天然就是递归的。你不需要关心"n-1 个盘具体怎么移"——那是更小规模的问题，让递归自己去解决。
#include <stdio.h>
// 汉诺塔：把 n 个盘从 from 柱，借助 aux 柱，移到 to 柱
// 参数：n 盘子数, from 起点柱, aux 辅助柱, to 终点柱
void Hanoi(int n, char from, char aux, char to)
{
if (n == 1) // 终止条件：只剩一个盘
{
printf("%c -> %c\n", from, to); // 直接移过去
return;
}
Hanoi(n - 1, from, to, aux); // ① 上面 n-1 个盘：from → aux（借助 to）
printf("%c -> %c\n", from, to); // ② 最大的盘：from → to
Hanoi(n - 1, aux, from, to); // ③ 那 n-1 个盘：aux → to（借助 from）
}
int main()
{
int n = 0;
printf("请输入盘子数：");
scanf("%d", &n);
Hanoi(n, 'A', 'B', 'C'); // 从 A 借助 B 移到 C
return 0;
}
/* 输入 3，输出：
* A -> C
* A -> B
* C -> B
* A -> C
* B -> A
* B -> C
* A -> C
* 共 7 步 */这个代码只有 10 行，但它解决的是"看起来无比复杂"的问题。 这就是递归的威力——描述问题的难度，被递归"翻译"成了代码的简洁。
你可以自己动手验证 n=3 的输出：每一步之后，检查三根柱子上的圆盘是否都满足"大不压小"的规则。你会发现这个 10 行函数给出的移动方案完全正确。
汉诺塔需要移动多少次？
设移动 n 个盘需要 f(n) 步。根据上面的拆解：
f(1) = 1
f(n) = f(n-1) + 1 + f(n-1) = 2*f(n-1) + 1
解这个递推式：f(n) = 2^n - 1。
- n=3：7 步
- n=5：31 步
- n=10：1023 步
- n=64：2^64 - 1 ≈ 1.8×10^19 步！
传说中"僧侣移动 64 层金盘，移完世界就毁灭"——按每秒移动一个盘计算，需要 5800 亿年。这个传说其实就是指数爆炸的文学化表达。看到 2^n 这种增长，任何计算机都无能为力——这就是为什么递归必须"大事化小"，而绝不能"大事化更多"。
经典递归问题（二）：青蛙跳台阶
这是另一个面试和笔试题的常客。问题描述：
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求青蛙跳上 n 级台阶总共有多少种跳法。
先手动算几个小规模：
- n=1：只有 1 种跳法（跳 1 级）；
- n=2：2 种（1+1，或者一次跳 2 级）；
- n=3：3 种（1+1+1，1+2，2+1）；
- n=4：5 种（你可以自己枚举一下）；
- n=5：8 种。
发现规律了吗？1, 2, 3, 5, 8……这正是斐波那契数列（去掉前两个 1）！为什么会这样？
关键思考：青蛙跳上第 n 级台阶，它的"最后一步"只有两种可能——要么从第 n-1 级跳 1 级上来，要么从第 n-2 级跳 2 级上来。所以：
f(n) = f(n-1) + f(n-2) （n > 2）
f(1) = 1
f(2) = 2
又是"大事化小"！跳 n 级台阶的问题，被分解成了"跳 n-1 级"和"跳 n-2 级"两个更小的同类问题。 这就是为什么它和斐波那契长得一模一样——它们的递归结构相同。
#include <stdio.h>
// 青蛙跳台阶：跳上 n 级台阶的跳法数
// 思路：
// 最后一步只能从 n-1 级跳 1 级，或从 n-2 级跳 2 级
// 所以 f(n) = f(n-1) + f(n-2)
int FrogJump(int n)
{
if (n <= 2) // 终止条件：1 级 1 种，2 级 2 种
return n;
else
return FrogJump(n - 1) + FrogJump(n - 2);
}
int main()
{
int n = 0;
printf("请输入台阶数：");
scanf("%d", &n);
int ways = FrogJump(n);
printf("跳上 %d 级台阶共有 %d 种跳法\n", n, ways);
return 0;
}
/* 输入 5，输出：跳上 5 级台阶共有 8 种跳法 */注意：既然它的本质是斐波那契，那么它也有斐波那契的毛病——纯递归版本会指数级重复计算，n 一大就卡死。所以这个题有两个层次：
- 面试答递归版：展示你能抓住递归结构（
f(n) = f(n-1) + f(n-2)），这是主要考察点； - 工程写迭代版：实际代码用循环从前往后推，O(n) 搞定：
// 迭代版：时间和空间都更优
int FrogJump2(int n)
{
int a = 1; // f(1)
int b = 2; // f(2)
int c = n; // 处理 n<=2 的情况直接返回
int i = 0;
for (i = 3; i <= n; i++)
{
c = a + b; // f(i) = f(i-1) + f(i-2)
a = b; // 前两项整体后移
b = c;
}
return c;
}变式：一次能跳 1~3 级呢？
把问题改一下：青蛙一次可以跳 1 级、2 级或 3 级，跳 n 级有多少种跳法？递归结构立刻变成：
f(n) = f(n-1) + f(n-2) + f(n-3)
f(1) = 1, f(2) = 2, f(3) = 4
发现没有——递归的威力在于：只要你能写出"最后一步有几种可能"，递推式就出来了。改一个条件，递推式加一项而已。这就是递归思想的通用性：它不解决具体某个问题，它给你一种"如何把大问题拆成小问题"的思维框架。
写递归的四个步骤——方法总结
看了这么多例子，现在总结一个"写递归的四步法"，以后遇到新问题照着走：
- 定义清楚函数：这个递归函数接收什么参数、返回什么？（比如
Fact(n)返回 n 的阶乘） - 找终止条件：问题小到什么程度可以直接给出答案？直接返回，不再递归。
- 找递推关系：
f(n)和f(n-1)（或更小规模）之间是什么关系？把"大事化小"用公式写出来。 - 验证边界：用 n=0、n=1、n=2 这几个小值手推一遍，确认结果正确。
用这个四步法重新审视青蛙跳台阶：函数 FrogJump(n) 返回跳法数；终止条件是 n<=2；递推关系是 f(n)=f(n-1)+f(n-2)；验证 n=3 得到 3 种——正确。四步走完，代码几乎就抄出来了。
递归的进阶话题
尾递归（了解即可）
有一种特殊的递归叫尾递归：递归调用是函数的最后一个操作，后面没有任何代码。比如：
// 尾递归版阶乘：用额外的参数 acc 保存中间结果
int FactTail(int n, int acc)
{
if (n == 0)
return acc;
return FactTail(n - 1, n * acc); // 递归调用是最后一步
}尾递归的意义在于：理论上编译器可以把"递归调用"优化成"循环"（复用同一个栈帧，栈不会增长），这叫尾调用优化（TCO）。但C 语言标准不保证任何编译器会做这个优化（GCC 在 O2 下通常会做，MSVC 在 x64 下也会做），所以写 C 代码时不要依赖尾调用优化——深层递归照样可能栈溢出。这个知识在函数式语言（Haskell、Scala）里才真正重要。
递归与树的天然联系
你可能听说过"递归和树是一对 CP"。原因很简单：树的结构本身就是递归定义的——一棵树由根节点和若干子树组成，子树还是一棵树。所以遍历树、计算树的深度、统计节点数……这些操作用递归写，代码会自然得可怕。以后学二叉树时，你会看到递归的第二次绽放。顺带一提，猜数字和扫雷里"点开空格自动展开一片"的功能，本质就是递归的洪水填充（flood fill）——你已经在不知不觉中用过递归的思想了。
递归 vs 迭代——决策清单
| 场景 | 推荐 | 原因 |
|---|---|---|
| 深度可控（几十层以内）且递归写法更清晰 | 递归 | 代码优雅，贴近问题本质 |
| 深度可能很大（几千层以上） | 迭代 | 避免栈溢出 |
| 存在大量重复子问题（如斐波那契） | 迭代或备忘录 | 避免指数级重复计算 |
| 问题本身就是递归结构（如汉诺塔、树遍历） | 递归 | 迭代版反而复杂难懂 |
一句话总结：递归是"思想的望远镜"（看清问题结构），迭代是"执行的加速器"（跑得又快又稳）。两者不是对立关系，而是互补——你需要同时掌握，按场景选择。
本篇思考题
- 用递归实现"逆序打印一个整数的每一位"（输入 1234 输出 4 3 2 1），提示：把 printf 放在递归调用之前。
- 汉诺塔的移动次数为什么是
2^n - 1？推导f(n) = 2*f(n-1) + 1的求解过程。 - 青蛙跳台阶的递归版为什么 n 一大就卡？改成迭代版后时间复杂度是多少？
- 写一个递归函数计算 1 到 n 的和
Sum(n)，然后和n*(n+1)/2对比结果。 Fact(0)会调用Fact(-1)吗？如果你的终止条件是n <= 1呢？哪种更安全？- 用递归求
x的y次方时，能不能把Power(n, k/2)的平方作为优化？试试写出"快速幂"的递归版（提示：分奇偶讨论）。 - 为什么说"尾递归在 C 语言里不能被依赖"？验证一下你的编译器是否做了优化。
参考答案与详解
1. 逆序打印整数的每一位（输入 1234 输出 4 3 2 1）
把 printf 放在递归调用之前，这样"打印"发生在"递"的阶段，自然得到倒序：
#include <stdio.h>
void PrintReverse(int n)
{
printf("%d ", n % 10); // 先打印当前最低位
if (n > 9) // 还有高位，继续递归
PrintReverse(n / 10);
}
int main()
{
PrintReverse(1234); // 输出：4 3 2 1
printf("\n");
return 0;
}推演：PrintReverse(1234) 先打印 4，再递归 PrintReverse(123) 打印 3，递归 12 打印 2，递归 1 打印 1。因为每次打印都在递归调用之前执行，所以是逆序；而正文"顺序打印"是把打印放到递归调用之后，靠"归"的过程回填，所以是正序。
2. 汉诺塔为什么是 2^n - 1？推导过程
设移动 n 个盘需要 f(n) 步。把 n 个盘从 A 移到 C 拆成三步：先 f(n-1) 步把上面 n-1 个盘移到辅助柱 B，再 1 步移最大的盘到 C，最后 f(n-1) 步把 B 上那 n-1 个盘移到 C。所以：
f(1) = 1
f(n) = f(n-1) + 1 + f(n-1) = 2·f(n-1) + 1
求解：两边同时加 1，得到整齐的等比数列 f(n)+1 = 2·f(n-1)+2 = 2·(f(n-1)+1)。令 g(n)=f(n)+1，则 g(n)=2·g(n-1)，是公比为 2 的等比数列。g(1)=f(1)+1=2，所以 g(n)=2^n，即 f(n)=2^n-1。验证：n=3 → 2³−1=7 步，正确。
3. 青蛙跳台阶递归版为什么 n 一大就卡？迭代版复杂度？
青蛙跳台阶本质是斐波那契结构 f(n)=f(n-1)+f(n-2)，纯递归会导致大量重复计算，时间复杂度 O(2^n) 指数爆炸，n 稍大就卡死。改成迭代（从前往后推）后，时间复杂度降到 O(n)、空间复杂度 O(1)：
int FrogJump2(int n) // 迭代版
{
int a = 1, b = 2, c = n; // a=f(1), b=f(2), c 兜底 n<=2 的情况
int i;
for (i = 3; i <= n; i++)
{
c = a + b; // f(i) = f(i-1) + f(i-2)
a = b;
b = c;
}
return c;
}4. 递归求 1 到 n 的和，并与公式对比
#include <stdio.h>
// 递归：Sum(n) = n + Sum(n-1)，n==0 时返回 0
int Sum(int n)
{
if (n == 0)
return 0;
return n + Sum(n - 1);
}
int main()
{
int n = 100;
printf("递归 Sum(%d) = %d\n", n, Sum(n));
printf("公式 n*(n+1)/2 = %d\n", n * (n + 1) / 2); // 两者一致
return 0;
}Sum(100) = 5050，用 100×101/2 也是 5050，两者结果完全相同。小 n 手推即可验证，n 大时直接用公式（O(1)）避免递归栈高。
5. Fact(0) 会调用 Fact(-1) 吗？n==0、n==1、n<=1 哪种终止条件更安全？
关键看终止条件能不能"接住"最小输入 0：
- 终止条件用
n == 0（返回 1）：Fact(0)直接命中return 1，不会调用Fact(-1)，安全； - 终止条件用
n == 1（返回 1）：Fact(0)不满足（0≠1），会走 else 分支算0 * Fact(-1)；而Fact(-1)也不满足n==1，继续算(-1) * Fact(-2)…… 一路对越来越小的负数递归，无限递归直到栈溢出。这才是"Fact(0)调到Fact(-1)"真正的来源； - 终止条件用
n <= 1（返回 1）：Fact(0)满足0<=1，也会直接返回 1，不会调Fact(-1)，同样安全。
结论：n == 0 最贴合数学定义（0! = 1）、语义最清晰，首选；n <= 1 能把 0 和 1 都兜住，也安全。真正危险的是把终止条件写成 n == 1——它接不住 0 和负数，会死递归。写递归时务必想清楚"最小的合法输入能不能被终止条件直接接住"。
6. 快速幂的递归版
Power(x, k) 中，当 k 为偶数时 x^k = (x^(k/2))^2，把指数劈成一半；k 为奇数时 x^k = x·(x^((k-1)/2))^2。这样每层只递归一次、规模减半，复杂度从 O(k) 降到 O(log k)：
#include <stdio.h>
// 快速幂递归版（仅针对非负指数 k）
double FastPow(int x, int k)
{
if (k == 0)
return 1.0;
double half = FastPow(x, k / 2); // 先算 x^(k/2)，只递归一次
if (k % 2 == 0)
return half * half; // k 偶：x^k = (x^(k/2))^2
else
return x * half * half; // k 奇：x^k = x * (x^((k-1)/2))^2
}
int main()
{
printf("%.0f\n", FastPow(2, 10)); // 1024
printf("%.0f\n", FastPow(3, 5)); // 243
return 0;
}对比朴素递归 x * FastPow(x, k-1)（O(k) 层），快速幂只递归 O(log k) 层，效率天壤之别。这正是"每次递归都向更小规模靠近、且一次能消掉一半"的典型。
7. 为什么尾递归在 C 里不能依赖？
尾递归指"递归调用是函数的最后一个操作、之后没有任何代码"。理论上编译器可做尾调用优化（TCO）——复用当前栈帧、把它优化成循环，栈不增长。但 C 语言标准并不保证任何编译器必须做这个优化（GCC 要到 -O2 才做、MSVC 分平台，且都可能不触发）。所以依赖 TCO 的代码不可移植，深层尾递归照样可能栈溢出。
验证方法：写 FactTail(int n, int acc)，分别用 -O0 和 -O2（GCC/Clang）编译后喂一个很大的 n（比如 n=100000），观察 -O0 会栈溢出、-O2 可能正常跑完——从而确认"它优化了才安全，不优化就险"。
小结
递归是编程世界里最富有魅力也最具挑战性的概念之一。它能用几行代码描述一个复杂问题的解法，但也可能在你不经意间引发栈溢出或性能灾难。学习递归的关键不是背诵写法，而是训练"大事化小"的思维习惯——当你遇到一个问题，先问自己：这个问题能不能拆成一个更小的同类问题？最小的那个问题能不能直接解决？如果两个答案都是"是"，递归的大门就向你敞开了。
这一篇里我们走了完整的路线：从递归的形式（函数调用自己）到递归的思想（大事化小），从"递"与"归"的执行过程到栈帧与栈溢出的底层机制，从斐波那契的"反面教材"（重复计算）到汉诺塔、青蛙跳台阶两个经典问题的完整剖析。你手里现在有了一把钥匙——四步法（定义函数、找终止条件、找递推关系、验证边界）——下次遇到任何递归题，先走这四步。
写递归时请永远记住那几条铁律：先写终止条件；保证每次递归都向终止条件靠近；深度不可控时果断换迭代；不要在递归函数里用 static 变量。当你学完递归，还有扫雷游戏里那个"点开空格自动展开周围一片"的功能等着你用递归去实现——掌握递归之后，可以回去挑战它了。
还没有评论 — 第一条由你来留。