递归函数
递归思想、阶乘/斐波那契/汉诺塔、栈溢出风险
递归函数
函数调用自身——递归让复杂问题（树遍历、分治算法）变得简洁优雅。但 C 的递归要格外小心栈溢出。
学完本章你将： 掌握递归思想、阶乘/斐波那契/汉诺塔、递归 vs 迭代。
递归的本质
c
#include <stdio.h>
// 阶乘：n! = n * (n-1)!
int factorial(int n) {
if (n <= 1) return 1; // 基准条件
return n * factorial(n - 1); // 递归调用
}
int main() {
printf("5! = %d\n", factorial(5)); // 120
return 0;
}每次递归调用都会在栈上分配新的栈帧。必须有停止条件，否则无限递归耗尽栈空间。
斐波那契数列
c
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// ⚠️ 这是 O(2^n) 的指数级复杂度！
// fib(50) 需要几十亿次调用，永远算不完。
// 实际开发用迭代或记忆化搜索。迭代版（更好）
c
int fibIter(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int t = a + b;
a = b;
b = t;
}
return b;
}汉诺塔
c
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("%c → %c\n", from, to);
return;
}
hanoi(n - 1, from, aux, to);
printf("%c → %c\n", from, to);
hanoi(n - 1, aux, to, from);
}
// hanoi(3, 'A', 'C', 'B');⚠️ 栈溢出风险： C 函数调用栈通常只有几 MB。递归深度超过 ~10 万就可能崩溃。深度递归考虑用堆上的手动栈替代。