递归与可变参数

概念说明

递归是函数在定义中直接或间接调用自己。 它适合描述具有相同子结构的问题，但必须有明确的结束条件，否则会无限调用下去。

递归的表达能力很强，但代价也很真实。 每多递归一层，就会多一层函数调用开销和栈空间消耗，所以它并不适合所有问题。

可变参数函数允许参数个数不固定，常见于 printf 这类接口。 在 C 里，这类函数通常要借助 stdarg.h 提供的 va_list、va_start、va_arg 和 va_end。

语法/规则

1. 递归函数至少需要“递归推进”和“终止条件”两个部分。
2. 如果递归深度较大，要考虑栈空间和重复计算带来的成本。
3. 可变参数函数通常至少需要一个固定参数，用来描述后续参数的个数或格式。
4. va_arg 读取参数时必须使用正确类型，否则结果不可预期。
5. 传入可变参数时要注意默认参数提升，例如 char、short 会提升为 int。
6. 处理完可变参数后要调用 va_end 完成收尾。
7. 如果一个问题能用简单循环表达，就不必为了“高级感”强行使用递归。

示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdarg.h>
#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int sum_ints(int count, ...) {
    va_list args;
    int sum = 0;

    va_start(args, count);
    for (int i = 0; i < count; i++) {
        sum += va_arg(args, int);
    }
    va_end(args);

    return sum;
}

int main(void) {
    printf("factorial = %d\n", factorial(5));
    printf("sum = %d\n", sum_ints(4, 1, 2, 3, 4));
    return 0;
}

输出结果：

1
2

factorial = 120
sum = 10

常见错误

1. 递归函数没有正确结束条件，导致栈不断增长直到程序崩溃。
2. 把本可复用的递归结果反复重复计算，导致时间开销急剧上升。
3. va_arg 读取的类型和实际传入类型不一致，造成未定义行为。
4. 写了可变参数函数却没有额外信息来判断参数个数，导致读取边界不清楚。
5. 忘记调用 va_end，或者在读取完成后继续使用已经失效的 va_list。