C语言编程题使用递归计算斐波那契数列的第n项

1、基本递归法

最基本的递归方法，通过直接递归计算第 n 项斐波那契数。

#include <stdio.h>

// 基本递归法计算斐波那契数列第 n 项
int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

2、带缓存的递归法（Memoization）

使用数组缓存已经计算过的斐波那契数，减少重复计算，提升性能。

#include <stdio.h>

// 全局数组，用于缓存已经计算的斐波那契数
int memo[1000];

// 带缓存的递归法计算斐波那契数列第 n 项
int fibonacci(int n) {
    if (n <= 1)
        return n;
    if (memo[n] != -1)  // 如果缓存中已经有结果，直接返回
        return memo[n];
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);  // 递归计算并缓存结果
    return memo[n];
}

int main() {
    int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);

    // 初始化缓存数组
    for (int i = 0; i <= n; i++)
        memo[i] = -1;

    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

3、尾递归优化法

尾递归是一种优化递归方法，通过将递归调用放在函数的最后一步，可以优化递归的内存使用。

#include <stdio.h>

// 尾递归优化法计算斐波那契数列第 n 项
int fibonacciTailRecursion(int n, int a, int b) {
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    return fibonacciTailRecursion(n - 1, b, a + b);
}

int fibonacci(int n) {
    return fibonacciTailRecursion(n, 0, 1);
}

int main() {
    int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

4、 矩阵快速幂法

使用矩阵快速幂来计算斐波那契数，效率更高。

#include <stdio.h>

void multiply(int F[2][2], int M[2][2]) {
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(int F[2][2], int n) {
    if (n == 0 || n == 1)
        return;

    int M[2][2] = {{1, 1}, {1, 0}};

    power(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0)
        multiply(F, M);
}

int fibonacci(int n) {
    if (n == 0)
        return 0;

    int F[2][2] = {{1, 1}, {1, 0}};
    power(F, n - 1);
    
    return F[0][0];
}

int main() {
    int n;
    printf("Enter the position of Fibonacci sequence: ");
    scanf("%d", &n);
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}