Mdr-C-Tutorial

主题

6.3 递归 ​

递归函数在执行过程中直接或间接调用自身。递归必须同时具备终止条件和使问题趋近终止条件的递归步骤。

1. 最小示例 ​

c
unsigned long long factorial(unsigned int n) {
    if (n < 2) {
        return 1;
    }
    return n * factorial(n - 1);
}

n < 2 是终止条件；factorial(n - 1) 让下一次调用处理更小的问题。

2. 调用栈 ​

每次尚未返回的调用都要保存自己的形参、局部对象和返回位置。递归层数过深会耗尽实现提供的调用栈空间，C 标准不保证能够完成任意深度的递归。

3. 递归与循环 ​

能用递归表达的问题通常也能通过显式状态和循环表达。递归适合描述天然嵌套的结构；循环通常更容易控制存储开销。选择哪一种形式，应由问题结构和可验证性决定。