递归陷阱七例

栈溢出

无限递归

大常数参数

递归深度过大

重复计算

函数调用开销

递归与迭代的选择

总结

递归是一种强大的编程技术，它允许函数调用自身。递归在很多情况下可以简化代码，使问题更容易理解和解决。然而，递归也容易导致一些常见的问题，这些问题被称为递归陷阱。本文将总结一些常见的递归陷阱，并提供示例代码来避免这些陷阱。

栈溢出

递归函数会在每次调用自身时创建一个新的栈帧。如果递归深度过大，可能会导致栈溢出。为了避免栈溢出，我们可以限制递归深度，或者使用尾递归优化。

示例代码：计算斐波那契数列

#include <stdio.h>

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

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

在上面的代码中，我们使用递归计算斐波那契数列。然而，这个递归函数的效率很低，因为它会重复计算很多子问题。为了避免栈溢出，我们可以使用动态规划或缓存技术来优化递归函数。

无限递归

递归函数必须有终止条件，否则它会无限递归下去。在编写递归函数时，一定要确保有正确的终止条件。

示例代码：计算阶乘

#include <stdio.h>

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

int main() {
    int n = 5;
    printf("Factorial %d = %d\n", n, factorial(n));
    return 0;
}

在上面的代码中，我们使用递归计算阶乘。这个递归函数有一个明确的终止条件：当n等于0时，返回1。这样，递归函数就可以正确地计算出阶乘。

大常数参数

递归函数的参数应该尽量小，以减少栈空间的使用。如果递归函数的参数过大，可能会导致栈溢出。

示例代码：计算幂

#include <stdio.h>

double power(double x, int n) {
    if (n == 0) {
        return 1;
    }
    return x * power(x, n - 1);
}

int main() {
    double x = 2.0;
    int n = 10;
    printf("%.2f^%d = %.2f\n", x, n, power(x, n));
    return 0;
}

在上面的代码中，我们使用递归计算幂。然而，这个递归函数的参数n是一个整数，如果n非常大，可能会导致栈溢出。为了避免这个问题，我们可以使用迭代而不是递归。

递归深度过大

有些问题本身就需要很深的递归深度才能解决。在这种情况下，我们可以尝试使用非递归算法，或者使用分治法将问题分解成更小的子问题。

示例代码：汉诺塔

#include <stdio.h>

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);
}

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

在上面的代码中，我们使用递归解决汉诺塔问题。这个问题需要很深的递归深度才能解决。为了避免栈溢出，我们可以限制递归深度，或者使用非递归算法。

重复计算

在递归函数中，可能会重复计算相同的子问题多次。为了避免重复计算，我们可以使用记忆化递归（也称为递归+缓存）。

示例代码：计算斐波那契数列（记忆化递归）

#include <stdio.h>
#include <stdlib.h>

int *fibCache;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    if (fibCache[n] != -1) {
        return fibCache[n];
    }
    fibCache[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return fibCache[n];
}

int main() {
    int n = 10;
    fibCache = (int *) calloc(n + 1, sizeof(int));
    for (int i = 0; i <= n; i++) {
        fibCache[i] = -1;
    }
    printf("Fibonacci %d = %d\n", n, fibonacci(n));
    free(fibCache);
    return 0;
}

在上面的代码中，我们使用记忆化递归计算斐波那契数列。我们创建了一个缓存数组fibCache来存储已经计算过的斐波那契数。在递归函数中，我们首先检查fibCache[n]是否已经计算过，如果已经计算过，就直接返回结果，否则计算fibCache[n]，并将结果存储在fibCache[n]中。

函数调用开销

递归函数的每次调用都会有一定的开销，包括参数传递、栈帧创建和销毁等。在递归深度较大时，这些开销可能会累积起来，影响程序的性能。为了避免这个问题，我们可以尝试减少递归深度，或者使用非递归算法。

示例代码：计算幂（迭代）

#include <stdio.h>

double power(double x, int n) {
    double result = 1.0;
    while (n > 0) {
        if (n % 2 == 1) {
            result *= x;
        }
        x *= x;
        n /= 2;
    }
    return result;
}

int main() {
    double x = 2.0;
    int n = 10;
    printf("%.2f^%d = %.2f\n", x, n, power(x, n));
    return 0;
}

在上面的代码中，我们使用迭代而不是递归计算幂。这个迭代算法的时间复杂度是O(log n)，与递归算法相当，但它避免了递归调用的开销。

递归与迭代的选择

在解决某些问题时，递归和迭代都是可行的选择。一般来说，递归更容易理解和实现，但可能会导致性能问题。而迭代可能更难理解和实现，但通常更高效。在选择递归还是迭代时，我们应该根据问题的性质和性能要求来决定。

示例代码：计算斐波那契数列（迭代）

#include <stdio.h>

int fibonacci(int n) {
    int a = 0, b = 1, temp;
    while (n > 0) {
        temp = a + b;
        a = b;
        b = temp;
        n--;
    }
    return a;
}

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

在上面的代码中，我们使用迭代计算斐波那契数列。这个迭代算法的时间复杂度是O(n)，与递归算法相当，但它避免了递归调用的开销。