递归

递归是函数调用自身的编程技术。一个正确的递归函数需要两个要素：基线条件（Base Case）——终止递归的条件；递归条件（Recursive Case）——函数调用自身解决更小的问题。递归让某些问题（如树遍历、分治算法）的表达更自然，但也带来栈空间开销和性能问题。

递归的原理

每次递归调用都会在调用栈上创建一个新的栈帧，包含独立的局部变量：

int factorial(int n)
{
    if (n <= 1)                 /* 基线条件 */
        return 1;
    
    return n * factorial(n - 1);    /* 递归条件 */
}

/* factorial(5) 的调用链：
   factorial(5) → 5 * factorial(4)
   factorial(4) → 4 * factorial(3)
   factorial(3) → 3 * factorial(2)
   factorial(2) → 2 * factorial(1)
   factorial(1) → 1
   
   回代：
   factorial(2) = 2 * 1 = 2
   factorial(3) = 3 * 2 = 6
   factorial(4) = 4 * 6 = 24
   factorial(5) = 5 * 24 = 120
*/

经典递归示例

阶乘：

int factorial(int n)
{
    if (n < 0) return -1;       /* 错误处理 */
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

斐波那契数列：

int fibonacci(int n)
{
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

/* 问题：大量重复计算 */
/* fib(5) = fib(4) + fib(3) */
/* fib(4) = fib(3) + fib(2) → fib(3) 计算两次！ */
/* 时间复杂度 O(2^n) */

二分查找：

int binary_search(int arr[], int left, int right, int target)
{
    if (left > right)
        return -1;              /* 未找到 */
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return binary_search(arr, left, mid - 1, target);
    else
        return binary_search(arr, mid + 1, right, target);
}

汉诺塔：

void hanoi(int n, char from, char to, char aux)
{
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    
    hanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

递归 vs 迭代

任何递归都可以改写为迭代，通常迭代更高效：

/* 递归阶乘 */
int factorial_recursive(int n)
{
    if (n <= 1) return 1;
    return n * factorial_recursive(n - 1);
}

/* 迭代阶乘 */
int factorial_iterative(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}
特性递归迭代
代码简洁性通常更简洁可能更冗长
栈空间每次调用消耗栈帧固定栈空间
性能有函数调用开销通常更快
适用场景树、分治、回溯线性遍历、简单循环

尾递归

尾递归是指递归调用是函数的最后一个操作。某些编译器可以优化尾递归，复用当前栈帧：

/* 普通递归：需要保存中间结果 */
int factorial(int n)
{
    if (n <= 1) return 1;
    return n * factorial(n - 1);      /* 递归后还有乘法 */
}

/* 尾递归：递归是最后操作 */
int factorial_tail(int n, int acc)
{
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  /* 递归是最后操作 */
}

int factorial(int n)
{
    return factorial_tail(n, 1);
}

注意：C 标准不保证尾递归优化，依赖它是不可移植的。需要避免栈溢出时，应显式使用迭代。

递归深度限制

栈空间有限，过深的递归会导致栈溢出：

/* 危险：n 很大时栈溢出 */
int factorial(int n)
{
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

/* 100000 的阶乘远超 64 位范围，且递归深度 100000 可能溢出 */

典型栈大小：

  • Linux 默认：8 MB
  • Windows 默认：1 MB
  • 嵌入式系统：可能只有几 KB

常见错误

缺少基线条件：

void infinite(void)
{
    infinite();             /* 无限递归 → 栈溢出 */
}

基线条件不可达：

int factorial(int n)
{
    if (n == 0) return 1;     /* 如果传入负数，永远达不到基线 */
    return n * factorial(n - 1);
}

/* factorial(-1) → 无限递归 */

重复计算：

int fibonacci(int n)
{
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);   /* 大量重复计算 */
}

/* fib(40) 需要约 2^40 次运算，非常慢 */

解决方案：记忆化

int fibonacci_memo(int n, int memo[])
{
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];     /* 已计算过 */
    
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
    return memo[n];
}

int fibonacci(int n)
{
    int memo[100];
    for (int i = 0; i < 100; i++) memo[i] = -1;
    return fibonacci_memo(n, memo);
}

最佳实践

  • 确保有可达的基线条件
  • 每次递归向基线条件推进
  • 考虑递归深度，避免栈溢出
  • 简单线性递归优先考虑迭代
  • 树遍历、分治、回溯等场景递归更自然
  • 尾递归不保证优化，不要依赖它避免栈溢出
  • 重复子问题考虑记忆化或动态规划