C语言递归函数

递归（Recursion）是一种重要的编程思想，指函数在其定义中直接或间接调用自身。 递归可以将复杂问题分解为规模更小的相同子问题，从而简化代码逻辑。 递归在树形结构遍历、分治算法、数学计算等领域有着广泛的应用。 本章将深入讲解递归的原理、经典示例以及递归与迭代的取舍。

🔄 什么是递归？

一个函数调用自身称为递归调用。递归函数通常包含两个部分：

• 基线条件（Base Case）：递归终止的条件，避免无限递归。
• 递归条件（Recursive Case）：函数调用自身，每次调用问题的规模逐渐减小，最终达到基线条件。

最简单的递归示例：计算阶乘。

#include <stdio.h>

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

int main() {
    int n = 5;
    printf("%d! = %lld\n", n, factorial(n));  // 输出 120
    return 0;
}

📚 递归的执行原理：函数调用栈

每次递归调用都会在内存的栈区中创建一个新的栈帧，用于存储局部变量、参数和返回地址。 递归调用逐层深入，当到达基线条件时开始逐层返回，栈帧依次弹出。 如果递归层次过深，会导致栈溢出（Stack Overflow）。

📖 经典递归示例

🔸 斐波那契数列

斐波那契数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。递归实现直观，但效率极低（重复计算）。

#include <stdio.h>

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

int main() {
    int n = 10;
    printf("F(%d) = %d\n", n, fibonacci(n));  // 55
    return 0;
}

🔸 汉诺塔问题

汉诺塔是一个经典的递归问题，目标是将n个盘子从A柱移动到C柱，借助B柱，每次只能移动一个盘子，且大盘不能放在小盘上。

#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("移动盘子 1 从 %c 到 %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);       // 将上面n-1个从from移到aux
    printf("移动盘子 %d 从 %c 到 %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);       // 将n-1个从aux移到to
}

int main() {
    int n = 3;
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

🔸 递归实现二分查找

在有序数组中查找目标值。

#include <stdio.h>

int binarySearch(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 binarySearch(arr, left, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, right, target);
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 45};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    int index = binarySearch(arr, 0, n - 1, target);
    printf("找到 %d 在索引 %d\n", target, index);
    return 0;
}

⚖️ 递归与迭代的比较

实际开发中，应根据具体问题选择。尾递归优化可以将递归转换为迭代，减少栈空间，但C语言标准未强制要求编译器实现尾递归优化。

🚀 尾递归（Tail Recursion）

尾递归是指递归调用是函数体中的最后一个操作，不需要保存当前函数的状态。某些编译器可以优化尾递归，将其转换为迭代，从而避免栈溢出。

阶乘的尾递归版本：

long long factorial_tail(int n, long long acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // 尾递归
}

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

✅ 递归的优点与缺点

• 优点：
  • 代码简洁，易于理解，特别是对于自然递归的问题（如树遍历、汉诺塔）。
  • 便于数学归纳式推导。
• 缺点：
  • 函数调用开销大，效率低。
  • 占用栈空间，深度过大可能导致栈溢出。
  • 难以调试，尤其当递归层次很深时。

📋 综合示例：快速幂（分治法）

快速幂算法利用分治思想，将幂运算从O(n)优化到O(log n)。

#include <stdio.h>

// 递归版快速幂
long long pow_recursive(long long base, long long exp) {
    if (exp == 0) return 1;
    if (exp == 1) return base;
    long long half = pow_recursive(base, exp / 2);
    if (exp % 2 == 0)
        return half * half;
    else
        return half * half * base;
}

// 迭代版快速幂（对比）
long long pow_iterative(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result *= base;
        base *= base;
        exp >>= 1;
    }
    return result;
}

int main() {
    printf("2^10 = %lld\n", pow_recursive(2, 10));   // 1024
    printf("3^5 = %lld\n", pow_iterative(3, 5));     // 243
    return 0;
}

⚠️ 常见错误与注意事项

• 缺少基线条件：导致无限递归，最终栈溢出程序崩溃。
• 递归条件没有向基线条件靠近：例如参数错误或不变，也会无限递归。
• 递归深度过大：超出栈空间，引发段错误。应估算递归深度，必要时改用迭代。
• 误用全局变量：在递归中修改全局变量可能导致意外的副作用，应尽量使用参数传递。
• 重复计算：如斐波那契的朴素递归，可使用记忆化（动态规划）优化。
• 返回局部变量地址：递归中返回指向局部变量的指针是危险的，因为该变量在函数返回后生命周期结束。

---

递归是一种强大的思维工具，能将复杂问题简化为更小规模的相同问题。 虽然递归在某些场景下不如迭代高效，但它的代码简洁性和数学美感使其在算法设计中占据重要地位。 掌握递归，将为后续学习树、图、分治算法等高级数据结构打下坚实基础。