什么是递归
递归是函数直接或间接调用自身的一种编程技巧，通常用于将问题分解为相似的子问题。
关键点：
基准条件（Base Case）：终止递归的条件，防止无限调用。递归条件（Recursive Case）：函数调用自身，逐步向基准条件逼近。
示例：阶乘
int factorial(int n) {
if (n == 0) return 1; // 基准条件
else return n * factorial(n - 1); // 递归条件
}
注意：
递归可能引发栈溢出（如深度过大）。某些问题（如斐波那契数列）用递归效率低，可改用迭代或记忆化优化。
递归的限制条件
递归的限制条件主要包括以下几点：
1. 基准条件（Base Case）
必须至少有一个明确的终止条件，否则递归会无限进行，导致栈溢出。示例：if (n == 0) return 1; // 阶乘递归的基准条件
2. 递归深度限制（Stack Overflow）
每次递归调用都会占用栈空间，深度过大会导致 栈溢出（Stack Overflow）。C语言默认栈空间有限（通常几MB），不适合过深递归（如数万层）。
3. 效率问题
递归可能重复计算（如斐波那契数列的朴素递归），时间复杂度高。某些情况可用 迭代（循环） 或 记忆化（缓存结果） 优化。
4. 间接递归需谨慎
若函数A调用B，B又调用A（间接递归），需确保最终能终止。
示例（错误递归，无基准条件）：
void infinite_recursion() {
infinite_recursion(); // 无限调用，导致栈溢出
}
总结：递归必须满足 基准条件 + 有限深度，否则可能崩溃或低效。
递归的常见举例
递归在C语言中常用于解决可分解为相似子问题的情况。以下是几个经典示例：
1. 阶乘（Factorial）
公式：n! = n × (n-1)!，基准条件 0! = 1
int factorial(int n) {
if (n == 0) return 1; // 基准条件
else return n * factorial(n - 1); // 递归调用
}
2. 斐波那契数列（Fibonacci）
公式：fib(n) = fib(n-1) + fib(n-2)，基准条件 fib(0)=0, fib(1)=1
int fib(int n) {
if (n <= 1) return n; // 基准条件
else return fib(n - 1) + fib(n - 2); // 递归调用（效率低，可优化）
}
注意：朴素递归会重复计算，实际应用需用 动态规划 或 迭代 优化。
3. 汉诺塔（Tower of Hanoi）
规则：将n个盘子从A柱移到C柱，每次只能移动一个盘子，且大盘不能压小盘。
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", from, to); // 基准条件
} else {
hanoi(n - 1, from, aux, to); // 将n-1个盘子移到辅助柱
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n - 1, aux, to, from); // 将n-1个盘子移到目标柱
}
}
4. 链表递归遍历
递归打印链表节点：
typedef struct Node {
int data;
struct Node* next;
} Node;
void printList(Node* node) {
if (node == NULL) return; // 基准条件
printf("%d ", node->data);
printList(node->next); // 递归调用
}
5. 二分查找（递归版）
前提：数组已排序。
int binarySearch(int arr[], int left, int right, int target) {
if (left > right) return -1; // 基准条件：未找到
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid; // 找到目标
else if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target); // 递归左半
else
return binarySearch(arr, mid + 1, right, target); // 递归右半
}
6. 计算数组和
int arraySum(int arr[], int n) {
if (n <= 0) return 0; // 基准条件
return arr[n - 1] + arraySum(arr, n - 1); // 递归求和
}
递归 vs 迭代的选择
递归：代码简洁，适合问题天然递归（如树、分治算法）。迭代：避免栈溢出，效率更高（如斐波那契数列改用循环）。
关键：确保递归有终止条件，且问题规模逐步减小！
递归与迭代
递归（Recursion）与迭代（Iteration）对比
递归和迭代都是重复执行代码的方式，但实现机制不同，适用于不同场景。
特性递归（Recursion）迭代（Iteration）基本思想函数调用自身，分解问题为更小的子问题使用循环结构（for/while）重复执行代码块终止条件必须定义明确的基准条件（Base Case），否则无限递归依赖循环条件，条件不满足时退出循环内存消耗每次递归调用占用栈空间，可能栈溢出（Stack Overflow）仅需固定内存，无额外函数调用开销代码可读性更简洁，接近数学定义（如阶乘、斐波那契）通常更冗长，但逻辑直接适用场景问题天然可递归分解（如树、分治、回溯）线性问题（如遍历数组）、需避免栈溢出的情况性能可能因重复计算（如斐波那契）或函数调用开销较慢通常更快，无额外函数调用开销
经典示例对比
1. 计算阶乘
递归实现
int factorial(int n) {
if (n == 0) return 1; // 基准条件
return n * factorial(n - 1); // 递归调用
}
迭代实现
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}
2. 斐波那契数列
递归实现（效率低，O(2ⁿ)）
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // 重复计算严重
}
迭代实现（高效，O(n)）
int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
如何选择？
用递归：
问题可自然分解为子问题（如汉诺塔、二叉树遍历）。代码简洁性比性能更重要（如快速排序、归并排序）。 用迭代：
需要避免栈溢出（如计算大数阶乘）。性能敏感场景（如斐波那契数列）。问题适合线性处理（如数组求和、查找）。
递归转迭代的技巧
递归通常可用 栈（Stack） 模拟调用过程转为迭代：
// 递归的深度优先搜索（DFS）转迭代（使用显式栈）
void dfs_iterative(Node* root) {
Stack stack;
stack.push(root);
while (!stack.empty()) {
Node* node = stack.pop();
process(node);
if (node->right) stack.push(node->right);
if (node->left) stack.push(node->left);
}
}
总结：
递归适合“分治”问题，迭代适合“线性”问题。递归需警惕栈溢出，迭代需注意循环条件。两者可相互转换，但各有最佳适用场景。