递归
递归（Recursion）是指一个函数在其定义或执行过程中直接或间接调用自身的编程技巧，核心思想是将复杂问题分解为规模更小但结构相同的子问题。
递归的基本概念
递归调用栈帧变化 — 以 factorial(3) 为例
fact(3)等待 fact(2) 返回 → 压栈
↓ 调用
fact(2)等待 fact(1) 返回 → 压栈
↓ 调用
fact(1)等待 fact(0) 返回 → 压栈
↓ 调用
fact(0) = 1基线条件！开始返回 → 出栈
↑ 逐层返回 (LIFO)
fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 3 × 2 × 1 × 1 = 6
橙色框(基线条件)→停止递归开始返回 | 栈帧按 LIFO 顺序弹出：最后入栈的最先返回
一个有效的递归函数必须包含两个关键要素：
| 要素 | 含义 | 示例（阶乘） |
|---|---|---|
| 基线条件 | 递归终止的条件，防止无限递归 | if (n == 0) return 1; |
| 递归条件 | 将问题分解为更小的子问题并调用自身 | return n * factorial(n-1); |
经典递归问题
阶乘
实例
#include <stdio.h>
/* 阶乘递归实现
n! = n × (n-1)!，基线条件: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* 基线条件 */
return n * factorial(n - 1); /* 递归条件 */
}
int main() {
printf("5! = %lld\n", factorial(5)); /* 输出: 120 */
return 0;
}
/* 阶乘递归实现
n! = n × (n-1)!，基线条件: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* 基线条件 */
return n * factorial(n - 1); /* 递归条件 */
}
int main() {
printf("5! = %lld\n", factorial(5)); /* 输出: 120 */
return 0;
}
斐波那契数列
实例
#include <stdio.h>
/* 朴素递归：大量重复计算，O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* 基线条件 */
return fib(n-1) + fib(n-2); /* 递归条件 */
}
/* 记忆化优化：缓存已计算结果，O(n) */
#define MAX 100
long long memo[MAX] = {0};
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* 已计算过，直接返回 */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
printf("fib(10) (朴素): %d\n", fib(10)); /* 输出: 55 */
printf("fibMemo(50) (记忆化): %lld\n", fibMemo(50)); /* 输出: 12586269025 */
return 0;
}
/* 朴素递归：大量重复计算，O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* 基线条件 */
return fib(n-1) + fib(n-2); /* 递归条件 */
}
/* 记忆化优化：缓存已计算结果，O(n) */
#define MAX 100
long long memo[MAX] = {0};
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* 已计算过，直接返回 */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
printf("fib(10) (朴素): %d\n", fib(10)); /* 输出: 55 */
printf("fibMemo(50) (记忆化): %lld\n", fibMemo(50)); /* 输出: 12586269025 */
return 0;
}
汉诺塔问题
实例
#include <stdio.h>
/* 汉诺塔递归求解
n 个盘子从 src 借助 aux 移动到 dst
步骤：n-1 个从 src→aux，最大的从 src→dst，n-1 个从 aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("盘子 1 从 %c 移动到 %c\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* n-1 个从 src 移到 aux */
printf("盘子 %d 从 %c 移动到 %c\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* n-1 个从 aux 移到 dst */
}
int main() {
printf("汉诺塔 (3 个盘子):\n");
hanoi(3, 'A', 'B', 'C');
/* 输出: 共 7 步 (2³-1)，最小步数 = 2ⁿ-1 */
return 0;
}
/* 汉诺塔递归求解
n 个盘子从 src 借助 aux 移动到 dst
步骤：n-1 个从 src→aux，最大的从 src→dst，n-1 个从 aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("盘子 1 从 %c 移动到 %c\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* n-1 个从 src 移到 aux */
printf("盘子 %d 从 %c 移动到 %c\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* n-1 个从 aux 移到 dst */
}
int main() {
printf("汉诺塔 (3 个盘子):\n");
hanoi(3, 'A', 'B', 'C');
/* 输出: 共 7 步 (2³-1)，最小步数 = 2ⁿ-1 */
return 0;
}
递归与迭代对比
| 维度 | 递归 | 迭代 |
|---|---|---|
| 代码可读性 | 高（接近数学定义） | 有时不如递归直观 |
| 执行效率 | 较低（栈帧开销） | 较高 |
| 空间开销 | O(递归深度) 栈空间 | O(1) |
| 栈溢出风险 | 有（深度过大时） | 无 |
| 适用结构 | 树、图的自然递归结构 | 数组等线性结构 |
尾递归是一种特殊形式的递归，即递归调用是函数体中执行的最后一个操作。某些编译器能对尾递归进行优化，将其转换为等价迭代以节省栈空间。但并非所有 C 编译器都默认开启此项优化。