用C语言两种方案打出递归实现Fibonacci数列的代码，并进行比较

方案一：常规递归法

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        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 fib[100] = {0};

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (fib[n] != 0) {
        return fib[n];
    } else {
        fib[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return fib[n];
    }
}

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

两种方案都是使用递归实现Fibonacci数列。方案一是常规递归法，每次递归都会计算前面两个数的和，时间复杂度是指数级别的，当n较大时，程序的运行时间会非常长。方案二是记忆化递归法，在每次递归时将计算过的数列值存储下来，下次递归时如果已经计算过，直接返回存储的值，避免重复计算。这种方法的时间复杂度是线性级别的，当n较大时，程序的运行时间明显比方案一要短很多。