C 递归（Recursion）

递归是函数调用自身来解决问题的方法。关键是“基例（终止条件）”与“递归式（规模缩小）”。

1. 基本结构

int fact(int n) {
    if (n <= 1) return 1;        // 基例
    return n * fact(n - 1);      // 递归式
}

2. 典型示例

• 斐波那契：f(n) = f(n-1) + f(n-2)（指数复杂度，需优化）
• 二分查找：分治法典型应用
• 树遍历：前序/中序/后序

3. 尾递归与优化

某些编译器可对尾递归优化为迭代，但不保证；C 中建议显式写迭代版本以控制栈使用。

4. 风险与注意

• 栈溢出：递归深度过大导致程序崩溃
• 重复计算：如斐波那契 naive 版本，可用记忆化或迭代
• 可测试性：为递归设计清晰的基例与边界条件

5. 迭代替代示例（阶乘）

int fact_iter(int n){
    int r = 1; for (int i=2;i<=n;++i) r*=i; return r;
}

6. 小结

递归表达自然，但需关注栈与性能；在工程中优先考虑可控的迭代实现或使用分治+尾递归优化策略。