C 语言递归：基线条件、阶乘与栈深度

调用自己的函数

C 函数调用自己没有任何障碍。函数体内可以看到它自己的名字，所以下面的写法是合法的：

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* calls itself - but never stops! */
}

但它也是错的。它会一直打印下去，打印到负数，直到程序崩溃。它缺少的是基线条件：在某个条件下，函数直接返回，不再调用自己。

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* base case: stop */
        printf("Liftoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* recursive case: a smaller problem */
}

int main(void) {
    countdown(5);
    return 0;
}

每个递归函数都恰好由这两部分组成：

• 基线条件：最小的输入，直接给出答案，不再进行调用。
• 递归情形：借助同一问题的一个严格更小的版本来解决问题。

“严格更小”正是大家容易出错的地方。countdown(n - 1) 每次调用都向 0 靠近一步。countdown(n) 不会；如果 n 可以永远停在 1，countdown(n / 2) 也不会。每条路径都必须让问题变小，否则永远到不了基线条件。

阶乘

标准的第一个例子。n! 等于 n × (n-1) × ... × 1，并规定 0! 等于 1。这个定义本身就是递归的：n! = n × (n-1)!。

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* base case: 0! and 1! are both 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* recursive case */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

跟踪 factorial(4)，看看答案是怎样拼出来的。调用一路向下，乘法则在返回的路上完成：

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (base case)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

在基线条件返回之前，什么都不会相乘。每个尚未完成的调用都在等待，各自保存着自己的 n，这一点值得牢记：这些等待中的调用都会占用内存。

注意返回类型。int 大约在 13! 时溢出，悄悄得出一个错误的数，C 不会检查。unsigned long long 能算到 20!，再往后就不行了，因为 21! 超出了 64 位。这里的限制不在递归，而在类型。

基线条件刻意使用 n <= 1 而不是 n == 1：factorial(0) 应该等于 1，<= 能处理这种情况。如果写成 n == 1，调用 factorial(0) 会递归到 -1、-2，永不终止。这很好地说明了一个“显然正确”的基线条件也可能漏掉某个输入。

斐波那契，以及为什么朴素版本是个陷阱

斐波那契是另一个经典例子：从 0 和 1 开始，每个数都是前两个数之和。递归定义几乎可以直接照写。

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld calls)\n", n, result, calls);
    }
    return 0;
}

看看调用次数。fib(10) 需要 177 次调用；fib(35) 需要将近 3000 万次。n 每增加 5，工作量就乘以大约 11。

原因在调用树里一目了然。fib(5) 调用 fib(4) 和 fib(3)；fib(4) 又调用了 fib(3)；而它们每一个都从头重新计算 fib(2)。没有任何结果被记住，同样的子问题被一遍又一遍地求解，调用次数大约按 1.6ⁿ 增长。这样算 fib(50) 要跑好几天；fib(100) 比宇宙的寿命还长。

循环版本保存最后两个值，是线性时间的：

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) 瞬间就返回了。这里的教训不是“递归很慢”，而是带有重叠子问题的递归很慢，除非你把答案记下来。在计算时把结果存到数组里（记忆化），递归版本也会变成线性时间。

调用栈与栈溢出

每次函数调用都需要一个地方来存放参数、局部变量和返回地址。这块存储叫作栈帧，调用开始时压入，返回时弹出。递归会把栈帧一层层叠起来：factorial(1000) 会同时有一千个活动的栈帧，每个都有自己的 n。

栈并不大。典型的默认大小是 1 至 8 MB，所以几万个栈帧就是现实中的上限，如果每个栈帧里有一个大的局部数组，上限还要低得多。超出之后程序就会崩溃：

Segmentation fault (core dumped)

这就是栈溢出，有两种途径会导致它：

无限递归：基线条件缺失或无法到达。这是 bug，程序会立刻崩溃：

int bad(int n) {
    return bad(n - 1);      /* no base case - crashes in a fraction of a second */
}

正确但太深：对一个有一百万个元素的列表，每个元素递归一次。逻辑没错，只是这种做法装不进栈里。改写成循环，或者调整结构让深度变成对数级（像二分查找和归并排序那样对半递归，一百万个元素的深度只有大约 20）。

有些编译器能把尾递归，即递归调用是函数最后做的一件事、之后没有待完成工作的情况，转换成循环，复用同一个栈帧。上面的 countdown 是尾递归；factorial 不是，因为调用返回后还要做乘法。但 C 并不强制要求这种优化，所以它是否发生取决于编译器和编译选项。永远不要写只有在优化器消除了尾调用时才能正常工作的 C 代码。

递归真正占优的地方

每个递归函数都可以改写成循环，对于简单的计数，循环显然更好。当数据本身是递归的，也就是一个结构包含着更小的自身副本时，递归才真正派上用场。

二分查找是个清晰的例子：查找一半，再查找那一半的一半。

#include <stdio.h>

/* returns the index of target, or -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* base case: nothing left */
    }
    int mid = low + (high - low) / 2;       /* avoids overflow on big indices */

    if (a[mid] == target) {
        return mid;                         /* base case: found it */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> index %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

这里有两个基线条件，这很正常：一个表示找到，一个表示查完。深度大约是 log₂(n)，所以即使有十亿个元素，也只需要三十个栈帧。

递归天然适合的其他场景：遍历树或链表、遍历目录、解析嵌套表达式，以及快速排序和归并排序这类分治排序。在这些场景中，递归代码都比用显式栈改写的循环更短，也更清晰。

用递归还是循环？

Use a loop when       the problem is linear - counting, summing, scanning
Use recursion when    the data is nested - trees, nested structures, divide and conquer
Rewrite recursion     if the depth can grow with the input size without bound
Never use recursion   when subproblems overlap, unless you memoize

两点实用提示。递归调用的开销比一次循环迭代略大，每次都要压入和弹出一个栈帧，所以对于频繁执行的简单循环，迭代版本在速度和内存上都更胜一筹。另外调试方式也不同：深层递归的栈跟踪是几百个看起来一模一样的栈帧，所以当某个调用迟迟不结束时，在入口处打印参数（就像上面的 calls 计数器那样）。

编写递归函数：检查清单

1. 先找出基线条件。 最小的输入是什么，它的答案是什么？如果你说不出来，这个函数就写不出来。
2. 假设递归调用是正确的。 不要在脑子里一层层跟踪，相信 factorial(n - 1) 会返回 (n-1)!，只写把它变成答案的那一步。
3. 检查每条路径都在缩小问题。 对每一种可能的输入，包括 0 和负数，每次递归调用都必须向基线条件靠近。
4. 检查深度。 在真实数据上大约会有多少层栈帧？几千层没问题，几百万层就不行。
5. 检查重叠。 如果同一个子问题被计算了两次，你就需要记忆化或者循环。