C语言用优化递归方法，求解斐波那契数列第n项的值

在C语言中，递归是一种直观的方法来计算斐波那契数列的第n项。然而，递归方法的效率较低，因为它涉及大量的重复计算。优化递归的一种常见方法是使用“记忆化”（Memoization）技术，它通过保存已计算的斐波那契数列的值来避免重复计算。

下面是使用记忆化技术的C语言代码示例，它使用了一个数组来存储已经计算过的斐波那契数列的值：

#include <stdio.h>

#define MAX 1000 // 定义数组最大值

// 初始化数组，用于存储已计算的斐波那契数列的值
int fib_cache[MAX];

// 使用记忆化技术的递归函数
int fib(int n) {
    if (n <= 1) {
        return n;
    }
    // 如果数组中已经存储了该值，则直接返回
    if (fib_cache[n] != -1) {
        return fib_cache[n];
    }
    // 否则，先计算前面的值，存储在数组中，然后返回
    fib_cache[n] = fib(n-1) + fib(n-2);
    return fib_cache[n];
}

int main() {
    int n = 40; // 示例：计算第40项
    // 初始化数组，未计算的位置设为-1
    for (int i = 0; i < MAX; i++) {
        fib_cache[i] = -1;
    }
    // 设置fib_cache[0]和fib_cache[1]的初始值
    fib_cache[0] = 0;
    fib_cache[1] = 1;

    printf("斐波那契数列第%d项的值是: %d\n", n, fib(n));
    return 0;
}

在这个例子中，我们首先定义了一个足够大的数组`fib_cache`来存储计算出的斐波那契数列的值。在递归函数`fib`中，如果需要计算的值已经存在于数组中，则直接返回该值，否则先计算并存入数组，再返回结果。这种方法避免了重复计算，大大提高了递归求解斐波那契数列的效率。