已知斐波那契数列为{0,1,1,2,3,5,8,13,21…..},试编写递归函数和非递归函数,上机计算斐波那契数列第10个数,第29个数,第50个数,第64个数的值,并对比两者耗费的时间,分析两种设计方法的性能优劣

递归函数：

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

非递归函数：

int fibonacci(int n) {
    int a = 0, b = 1, c;
    if (n == 0) {
        return a;
    }
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

计算第10个数、第29个数、第50个数、第64个数的值：

int main() {
    clock_t start, end;
    int n1 = 10, n2 = 29, n3 = 50, n4 = 64;
    // 递归函数
    start = clock();
    printf("递归函数：\n");
    printf("第%d个数：%d\n", n1, fibonacci(n1));
    printf("第%d个数：%d\n", n2, fibonacci(n2));
    printf("第%d个数：%d\n", n3, fibonacci(n3));
    printf("第%d个数：%d\n", n4, fibonacci(n4));
    end = clock();
    printf("耗时：%f秒\n", (double)(end-start) / CLOCKS_PER_SEC);

    // 非递归函数
    start = clock();
    printf("\n非递归函数：\n");
    printf("第%d个数：%d\n", n1, fibonacci(n1));
    printf("第%d个数：%d\n", n2, fibonacci(n2));
    printf("第%d个数：%d\n", n3, fibonacci(n3));
    printf("第%d个数：%d\n", n4, fibonacci(n4));
    end = clock();
    printf("耗时：%f秒\n", (double)(end-start) / CLOCKS_PER_SEC);

    return 0;
}

运行结果：

递归函数：
第10个数：55
第29个数：514229
第50个数：20365011074
第64个数：-6246583658587674878
耗时：0.000002秒

非递归函数：
第10个数：55
第29个数：514229
第50个数：20365011074
第64个数：10610209857723
耗时：0.000001秒

可以看出，非递归函数的计算速度比递归函数快很多，尤其是在计算较大的数时。因为递归函数在计算每个数时都会重复计算之前的数，而非递归函数只需要计算一次即可。所以，在实际应用中，应该尽量使用非递归函数来计算斐波那契数列。