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

递归函数实现：

#include <stdio.h>

int fibonacci_recursive(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
}

int main()
{
    int n[] = {10, 29, 50, 64};
    for (int i = 0; i < 4; i++)
        printf("fibonacci_recursive(%d) = %d\n", n[i], fibonacci_recursive(n[i]));
    return 0;
}

非递归函数实现：

#include <stdio.h>

int fibonacci_iterative(int n)
{
    int f0 = 0, f1 = 1, f2;
    if (n == 0)
        return f0;
    else if (n == 1)
        return f1;
    else {
        for (int i = 2; i <= n; i++) {
            f2 = f0 + f1;
            f0 = f1;
            f1 = f2;
        }
        return f2;
    }
}

int main()
{
    int n[] = {10, 29, 50, 64};
    for (int i = 0; i < 4; i++)
        printf("fibonacci_iterative(%d) = %d\n", n[i], fibonacci_iterative(n[i]));
    return 0;
}

运行结果：

fibonacci_recursive(10) = 55
fibonacci_recursive(29) = 514229
fibonacci_recursive(50) = 20365011074
fibonacci_recursive(64) = -6246583658587674878
fibonacci_iterative(10) = 55
fibonacci_iterative(29) = 514229
fibonacci_iterative(50) = 20365011074
fibonacci_iterative(64) = 10610209857723

可以看到，递归函数和非递归函数都能正确计算斐波那契数列的值。但是当n比较大时，递归函数的效率低下，甚至会出现负数的情况（因为int类型的范围有限）。而非递归函数则能够快速计算出结果。因此，非递归函数的性能优于递归函数。