C语言如何实现Fibonacci数列算法？

斐波那契数列是一个非常经典的数学序列，在编程中常作为入门练习,它的定义是：

• 第0项 F(0) = 0
• 第1项 F(1) = 1
• 从第2项开始，每一项都等于前两项之和：F(n) = F(n-1) + F(n-2)

这个数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

在C语言中，实现斐波那契数列有多种方法，每种方法都有其优缺点和适用场景,下面我将介绍三种最常见的方法：

1. 递归法：最直观,但效率极低。
2. 迭代法（循环法）：高效且节省内存,是实际应用中最常用的方法。
3. 数组存储法：可以一次性计算出所有项,适合需要多次查询的场景。

递归法

递归的思想是把一个大问题分解成一个或多个与原问题结构相同但规模更小的子问题,直到子问题可以直接解决。

对于斐波那契数列，F(n) 的问题可以分解为 F(n-1) 和 F(n-2) 两个子问题。

C语言代码实现

#include <stdio.h>
// 递归函数，计算第n个斐波那契数
long long fibonacci_recursive(int n) {
    // 基本情况：当n为0或1时，直接返回对应的值
    if (n <= 1) {
        return n;
    }
    // 递归步骤：调用函数自身来解决更小的子问题
    else {
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
    }
}
int main() {
    int n;
    printf("请输入一个非负整数: ");
    scanf("%d", &n);
    if (n < 0) {
        printf("输入错误，请输入非负整数，\n");
    } else {
        printf("使用递归法计算: 第 %d 项斐波那契数是: %lld\n", n, fibonacci_recursive(n));
    }
    return 0;
}

优点与缺点

• 优点：
  • 代码简洁，逻辑清晰：代码几乎直接翻译了数学定义,非常容易理解。
• 缺点：
  • 效率极低：存在大量的重复计算，计算 fib(5) 时，fib(3) 会被计算两次，fib(2) 会被计算三次，随着 n 的增大,计算量呈指数级增长。
  • 栈溢出风险：每次函数调用都会在调用栈上占用空间，当 n 很大时（n > 40），递归深度会非常大，可能导致栈溢出,程序崩溃。

注意：这里使用了 long long 类型来存储结果，因为斐波那契数增长非常快，int 类型很快就会溢出。

迭代法（循环法）

迭代法使用循环来逐步计算，避免了递归带来的重复计算和栈溢出问题,这是最推荐的方法。

我们从数列的开头开始，一步步向后计算，直到得到第 n 项。

C语言代码实现

#include <stdio.h>
// 迭代函数，计算第n个斐波那契数
long long fibonacci_iterative(int n) {
    // 处理基本情况
    if (n <= 1) {
        return n;
    }
    long long a = 0; // 代表 F(0)
    long long b = 1; // 代表 F(1)
    long long c;     // 将用于存储 F(n)
    // 从第2项开始循环，计算到第n项
    // 循环 n-1 次
    for (int i = 2; i <= n; i++) {
        c = a + b;       // 计算当前项
        a = b;           // 更新 a 为前一项的值
        b = c;           // 更新 b 为当前项的值
    }
    return b; // 循环结束后，b 中存储的就是 F(n)
}
int main() {
    int n;
    printf("请输入一个非负整数: ");
    scanf("%d", &n);
    if (n < 0) {
        printf("输入错误，请输入非负整数，\n");
    } else {
        printf("使用迭代法计算: 第 %d 项斐波那契数是: %lld\n", n, fibonacci_iterative(n));
    }
    return 0;
}

优点与缺点

• 优点：
  • 效率高：时间复杂度为 O(n)，只需一个简单的循环,没有重复计算。
  • 节省内存：空间复杂度为 O(1)，只使用了几个变量来存储中间结果,不会占用大量栈空间。
• 缺点：
  • 代码稍复杂：相比递归，需要维护几个变量,逻辑上不如递归直观。

数组存储法

如果你需要多次查询斐波那契数列中的不同项，或者一次性计算出前 n 项,那么使用数组来存储所有计算结果是一个很好的选择。

C语言代码实现

#include <stdio.h>
// 数组存储法，计算前n项斐波那契数并存储在数组中
void fibonacci_array(int n, long long fib_array[]) {
    fib_array[0] = 0;
    if (n >= 1) {
        fib_array[1] = 1;
    }
    // 从第2项开始，利用循环和数组填充
    for (int i = 2; i <= n; i++) {
        fib_array[i] = fib_array[i - 1] + fib_array[i - 2];
    }
}
int main() {
    int n;
    printf("请输入一个非负整数: ");
    scanf("%d", &n);
    if (n < 0) {
        printf("输入错误，请输入非负整数，\n");
    } else {
        // 定义一个足够大的数组来存储结果
        long long fib_sequence[n + 1]; // C99标准支持变长数组
        fibonacci_array(n, fib_sequence);
        printf("使用数组法计算: 前 %d 项斐波那契数列是:\n", n + 1);
        for (int i = 0; i <= n; i++) {
            printf("%lld ", fib_sequence[i]);
        }
        printf("\n");
        // 如果你想单独获取第n项
        printf("第 %d 项斐波那契数是: %lld\n", n, fib_sequence[n]);
    }
    return 0;
}

优点与缺点

• 优点：
  • 查询速度快：一旦计算完成，获取任何一项的时间复杂度都是 O(1),只需访问数组即可。
  • 可以一次性获取所有项：非常适合需要遍历整个数列的场景。
• 缺点：
  • 占用内存：空间复杂度为 O(n)，需要创建一个大小为 n+1 的数组来存储结果。n 非常大,会消耗较多内存。

总结与对比

对于大多数编程问题，特别是需要计算较大 n 值的斐波那契数时，迭代法是最佳选择，它在性能和内存使用上都表现优异，是实际工程应用中的标准做法，递归法虽然优雅，但其性能瓶颈决定了它只适合教学演示，数组法则在特定需求下（如需要缓存结果）非常有用。