C: 函数进阶
递归就像两面相对的镜子——图像不断嵌套自身，直到远处的光点消失。函数调用自身解决问题，靠的就是这种层层缩小的力量。
1. 递归原理
递归是函数直接或间接调用自身的编程技术。每个递归必须具备两个要素：
- 递归条件：问题可以分解为规模更小的同类子问题
- 终止条件（基线条件）：最小子问题有直接答案，不再递归
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
以factorial(4)为例，执行过程：
factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24
2. 经典递归案例
(1) 阶乘
n的阶乘定义：n! = n × (n-1)!，且0! = 1。
long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
注意long类型能容纳的范围有限，factorial(20)已接近64位上限。
(2) 斐波那契数列
斐波那契定义：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。
long fib(int n) {
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}
fib(40)需要上亿次调用，因为大量子问题被重复计算。实际应用中应该用循环或记忆化优化。
(3) 汉诺塔
将n个盘子从柱A移到柱C，借助柱B，规则：大盘不能放在小盘上。
#include <stdio.h>
void hanoi(int n, char from, char mid, char to) {
if (n == 1) {
printf("%c -> %c\n", from, to);
return;
}
hanoi(n - 1, from, to, mid);
printf("%c -> %c\n", from, to);
hanoi(n - 1, mid, from, to);
}
int main(void) {
hanoi(3, 'A', 'B', 'C');
return 0;
}
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
思路：先把上面n-1个盘子移到辅助柱，把最大盘移到目标柱，再把n-1个盘子从辅助柱移到目标柱。3个盘子需要7步，n个盘子需要2^n - 1步。
▶ 示例
递归求整数各位数字之和：
#include <stdio.h>
int digit_sum(int n) {
if (n < 10) return n;
return n % 10 + digit_sum(n / 10);
}
int main(void) {
printf("%d\n", digit_sum(12345));
printf("%d\n", digit_sum(7));
return 0;
}
15
7
digit_sum(12345) = 5 + digit_sum(1234) = 5 + 4 + digit_sum(123) = ... = 5+4+3+2+1 = 15。
3. 变量作用域
作用域决定变量在哪些代码区域可见可用。
(1) 块作用域
在{}内定义的变量只在该块内可见，块结束即销毁：
int main(void) {
int x = 10;
{
int y = 20;
printf("%d %d\n", x, y);
}
printf("%d\n", x);
return 0;
}
y只在内层块中存在，外层无法访问。
(2) 文件作用域
在所有函数外定义的变量具有文件作用域，从定义位置到文件末尾都可见，称为全局变量：
int count = 0;
void increment(void) {
count++;
}
int main(void) {
increment();
increment();
printf("%d\n", count);
return 0;
}
(3) 同名遮蔽
内层作用域的变量会遮蔽外层同名变量：
int x = 100;
int main(void) {
int x = 10;
printf("%d\n", x);
return 0;
}
输出10，内层x遮蔽了全局x。全局x在内层块中无法直接访问。
4. 存储类
存储类决定变量的生命周期和可见性。C语言有四个存储类关键字：auto、static、extern、register。
(1) auto
auto是局部变量的默认存储类，通常省略不写。变量在进入块时创建，退出块时销毁：
void func(void) {
auto int x = 10;
}
等价于int x = 10;。
(2) static
static修饰局部变量时，变量在程序运行期间始终存在，但作用域仍限于函数内部。关键特性：只初始化一次，后续调用保留上次的值。
#include <stdio.h>
void counter(void) {
static int count = 0;
count++;
printf("第 %d 次调用\n", count);
}
int main(void) {
counter();
counter();
counter();
return 0;
}
第 1 次调用
第 2 次调用
第 3 次调用
如果没有static，count每次都会重新初始化为0，永远只打印"第1次"。
static修饰全局变量或函数时，将其可见性限制在当前文件内（内部链接），其他源文件无法通过extern访问。
(3) extern
extern用于声明一个在其他源文件中定义的全局变量，告诉编译器"这个变量存在，但不在当前文件定义"：
file1.c:
int shared_data = 42;
file2.c:
#include <stdio.h>
extern int shared_data;
int main(void) {
printf("%d\n", shared_data);
return 0;
}
extern不分配内存，只是声明。多文件项目中共享全局数据时需要extern。
(4) register
register建议编译器将变量存放在CPU寄存器中以提高访问速度：
void fast_loop(void) {
register int i;
for (i = 0; i < 1000000; i++) {
}
}
现代编译器的优化能力很强，通常会自动把频繁使用的变量放入寄存器，register提示的作用已不大。注意：不能对register变量取地址（&），因为寄存器没有内存地址。
▶ 示例
用static变量实现斐波那契（避免递归的重复计算）：
#include <stdio.h>
long fib_iter(int n) {
if (n <= 2) return 1;
long prev = 1;
long curr = 1;
long next;
int i;
for (i = 3; i <= n; i++) {
next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
int main(void) {
int i;
for (i = 1; i <= 10; i++) {
printf("F(%d) = %ld\n", i, fib_iter(i));
}
return 0;
}
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55
这个迭代版本时间复杂度O(n)，远优于朴素递归的O(2^n)。
❓ 常见问题
📖 小节
- 递归必须包含终止条件，否则栈溢出
- 朴素斐波那契递归效率低，实际问题需用循环或记忆化优化
- 局部变量具有块作用域，全局变量具有文件作用域
- static局部变量生命周期贯穿程序始终，但作用域不变
- extern实现跨文件共享变量，register在现代编译器中意义不大
📝 作业
- 编写递归函数
void print_reverse(int n)，逆序输出正整数各位（如123输出3 2 1）。 - 编写函数用static变量统计自身被调用的次数，并在main中调用5次后打印统计结果。
- 用递归实现二分查找：在已排序数组中查找目标值，找到返回下标，未找到返回-1。
