【C】-递归
1、递归概念
递归（Recursion）是编程中一种重要的解决问题的方法，其核心思想是函数通过调用自身来解决规模更小的子问题，直到达到最小的、可以直接解决的基准情形（Base Case）。
核心：自己调用自己
必要条件：
- 基准情形（base case）：函数不再递归调用的终止条件，避免无限循环；
- 递归步骤（Recursive step）：将原问题分解为规模更小的子问题，并通过递归调用解决。（每次递归调用后，越来越接近终止条件）.
2、递归的应用场合
- 数学问题：阶乘计算、斐波那契数列、最大公约数
- 数据结构遍历：树的遍历、图的深度优化搜索、链表操作（反转、查找）
- 分治算法：快速排序、归并排序、汉诺塔问题
- 其它：目录结构遍历、格式解析（JSON/XML）
3、递归的实现
/* 阶乘函数 */
int factorial(int n) {// 基准情形if (n == 0) return 1;// 递归步骤return n * factorial(n - 1);
}/* 二叉树遍历，前序 */
struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;
};void preOrderTraversal(struct TreeNode* root) {if (root == NULL) return; // 基准情形printf("%d ", root->data); // 访问根节点preOrderTraversal(root->left); // 递归左子树preOrderTraversal(root->right); // 递归右子树
}尾递归（Tail Recursion）
尾递归是递归编程的一种特殊形式，其核心特点是：递归调用是函数的最后一个操作，且返回值不参与任何计算。这种结构允许编译器将递归优化为迭代，避免栈溢出风险。
（1）普通递归 vs 尾递归
// 普通递归阶乘（非尾递归）：递归调用后还需进行额外计算（如乘法、加法）
int fact(int n) {if (n == 0) return 1;return n * fact(n-1); // 递归调用后需进行乘法运算
}// 尾递归阶乘：递归调用是最后一步，结果直接返回。
int fact_tail(int n, int acc) {if (n == 0) return acc;return fact_tail(n-1, n * acc); // 递归调用是最后操作，无后续计算
}
（2）关键特征
- 最后操作：递归调用必须是函数的最后一条语句。
- 无后续计算：返回值直接来自递归调用，不参与额外运算。
- 累加器参数：通常引入额外参数（如acc）保存中间结果
（3）尾递归的优缺点
优点
- 避免栈溢出：优化后等效于迭代，栈空间复杂度为 O (1)。
- 代码简洁：保持递归的逻辑清晰性，同时获得迭代的性能。
缺点
- 依赖编译器优化：C 语言标准并未强制要求尾递归优化，部分编译器（如 GCC）会自动优化，但并非所有平台都支持。
- 可读性降低：引入累加器参数可能使代码更难理解（如斐波那契的尾递归版本）。
4、递归的优缺点
优点
- 代码简洁：直接表达问题的数学定义，减少代码量。
- 易于理解：对于递归定义的问题（如树结构），逻辑更清晰。
- 解决复杂问题：适合分治策略，如排序和搜索算法。
缺点 - 性能开销：递归调用会消耗栈空间，可能导致栈溢出（Stack Overflow）。
- 效率问题：某些递归（如斐波那契数列）存在大量重复计算，可用 记忆化（Memoization） 优化。
- 调试困难：多层递归调用的执行流程复杂，调试时堆栈跟踪较深。
5、常见相关问题
（1）必须确保基准情形存在，否则会导致无限递归，最终引发栈溢出。
（2）注意递归深度，过深建议调整为循环或迭代。
（3）使用打印语句跟踪递归过程，或结合调试器查看调用栈。