C语言函数递归详解：递归条件、调用过程与迭代对比

C语言函数递归详解

1. 递归是什么

递归是函数直接或间接调用自身，把复杂问题不断缩小为结构相同的子问题。

一个正确的递归通常包含：

  1. 基准条件：在某种情况下停止递归；
  2. 递推关系：把当前问题转化为规模更小的问题；
  3. 规模收敛：每次调用都必须靠近基准条件。

2. 阶乘

数学定义：

1
2
0! = 1
n! = n × (n-1)!，n > 0
1
2
3
4
5
6
long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

计算 factorial(4) 时，调用逐层展开：

1
2
3
4
5
factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)

遇到基准条件后，再逐层返回结果。

3. 递归打印整数

1
2
3
4
5
6
void print_digits(unsigned int n)
{
    if (n > 9)
        print_digits(n / 10);
    printf("%u ", n % 10);
}

输入 1234 时，先递归处理高位，再在回归阶段从高位到低位输出。

4. 递归求字符串长度

1
2
3
4
5
6
size_t string_length(const char *str)
{
    if (*str == '\0')
        return 0;
    return 1 + string_length(str + 1);
}

每次把指针移动到下一个字符，直到遇到字符串结束标志 \0。

5. 递归与迭代

阶乘的迭代版本：

1
2
3
4
5
6
7
long long factorial_iterative(int n)
{
    long long result = 1;
    for (int i = 1; i <= n; ++i)
        result *= i;
    return result;
}
对比项 递归 迭代
表达能力 接近数学定义，适合树与分治 流程直接
空间 消耗调用栈 通常为常量额外空间
风险 递归过深可能栈溢出 较少出现栈深问题
性能 有函数调用开销 通常更高效

6. 斐波那契数列的陷阱

朴素递归：

1
2
3
4
5
6
long long fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

它会重复计算大量子问题，时间复杂度接近指数级。迭代写法更合适：

1
2
3
4
5
6
7
8
9
10
11
12
13
long long fib_iterative(int n)
{
    if (n <= 1)
        return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i)
    {
        long long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

7. 常见问题

  • 没有基准条件，导致无限递归；
  • 问题规模没有缩小，永远无法到达出口；
  • 递归层数太深，引发栈溢出；
  • 在递归中进行重复计算，导致性能极差；
  • 忽略负数、溢出等输入边界。

8. 适用场景

递归适合具有天然层次结构的问题，例如二叉树遍历、目录遍历、回溯、快速排序和归并排序。对于简单线性重复，循环通常更直接、更稳定。

9. 总结

理解递归要同时看到“向下展开”和“向上回归”。写递归前先明确出口、递推关系和规模变化，再评估调用深度与重复计算成本。