C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

斐波那契数列是指数列：1、1、2、3、5、8、13、21、…… 在数学上，斐波那契数列是以递归的方法来定义的，首两项为 1，之后每一项都是其前两项之和，即：
F(1) = 1, F(2) = 1
F(n) = F(n-1) + F(n-2) , n > 2

递归实现

递归是最贴近人类思维的一种算法实现方式，同时，也是易于理解、易于调试的一种方式。

递归实现斐波那契数列代码如下：

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

该方法的时间复杂度为O(2^n)，存在重复计算，容易造成栈溢出问题，因此在实际使用中需谨慎。

循环实现

循环实现方式通过定义两个变量a和b，每次循环将a和b的值依次赋值为b、a+b，实现了斐波那契数列的计算。

循环实现代码如下：

int fibonacci_loop(int n) {
    int a = 0, b = 1, sum;
    for(int i = 0; i < n; i++){
        sum = a + b;
        a = b;
        b = sum;
    }
    return a;
}

矩阵实现

矩阵实现方式是一种高效的斐波那契数列计算方式。该方法通过矩阵乘法的运算来计算每一项的值，时间复杂度达到了O(logn)的级别。

矩阵实现代码如下：

void matrix_multiply(long long a[][2], long long b[][2]) {
    long long m = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    long long n = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    long long p = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    long long q = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    a[0][0] = m; a[0][1] = n; a[1][0] = p; a[1][1] = q;
}

int fibonacci_matrix(int n) {
    long long ans[2][2] = {{1, 0}, {0, 1}}; //单位矩阵
    long long base[2][2] = {{1, 1}, {1, 0}}; //转移矩阵
    while (n > 0) {
        if (n & 1) {
            matrix_multiply(ans, base);
        }
        matrix_multiply(base, base);
        n >>= 1;
    }
    return ans[0][1];
}

示例说明

示例一：计算第十项斐波那契数列的值

分别调用三种实现方式的函数，得到第十项斐波那契数列的值如下：

int main() {
    int n = 10;
    printf("递归方式结果：%d\n", fibonacci_recursion(n));
    printf("循环方式结果：%d\n", fibonacci_loop(n));
    printf("矩阵方式结果：%d\n", fibonacci_matrix(n));
    return 0;
}

运行结果：

递归方式结果：55
循环方式结果：55
矩阵方式结果：55

示例二：计算前10项斐波那契数列的值

使用循环方式实现，计算并输出前10项斐波那契数列的值如下：

int main() {
    int n = 10;
    for (int i = 1; i <= n; i++) {
        printf("%d\t", fibonacci_loop(i));
    }
    printf("\n");
    return 0;
}

运行结果：

1       1       2       3       5       8       13      21      34      55