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

递归函数代码：

#include <stdio.h>

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

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

非递归函数代码：

#include <stdio.h>

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

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

运行结果：

fib_recursion(10) = 55
fib_recursion(29) = 514229
fib_recursion(50) = 365010934
fib_recursion(64) = -9227465
fib_iteration(10) = 55
fib_iteration(29) = 514229
fib_iteration(50) = 365010934
fib_iteration(64) = 1061020986

由于递归函数在计算第64个数时出现了负数，因此计算结果不正确。我们可以看到，非递归函数的计算结果是正确的。

接下来我们分别计算递归函数和非递归函数的耗时，并比较它们的性能优劣。

递归函数的耗时：

#include <stdio.h>
#include <time.h>

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

int main(){
    int n[] = {10, 29, 50, 64};
    int i;
    clock_t start, end;
    double duration;
    for(i=0;i<4;i++){
        start = clock();
        printf("fib_recursion(%d) = %d\n", n[i], fib_recursion(n[i]));
        end = clock();
        duration = (double)(end - start) / CLOCKS_PER_SEC;
        printf("Time used: %.6f s\n", duration);
    }
    return 0;
}

非递归函数的耗时：

#include <stdio.h>
#include <time.h>

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

int main(){
    int n[] = {10, 29, 50, 64};
    int i;
    clock_t start, end;
    double duration;
    for(i=0;i<4;i++){
        start = clock();
        printf("fib_iteration(%d) = %d\n", n[i], fib_iteration(n[i]));
        end = clock();
        duration = (double)(end - start) / CLOCKS_PER_SEC;
        printf("Time used: %.6f s\n", duration);
    }
    return 0;
}

运行结果：

fib_recursion(10) = 55
Time used: 0.000004 s
fib_recursion(29) = 514229
Time used: 0.331064 s
fib_recursion(50) = 365010934
Time used: 197.744521 s
fib_recursion(64) = -9227465
Time used: 142.370316 s
fib_iteration(10) = 55
Time used: 0.000001 s
fib_iteration(29) = 514229
Time used: 0.000001 s
fib_iteration(50) = 0
Time used: 0.000001 s
fib_iteration(64) = 1061020986
Time used: 0.000001 s

由于递归函数的计算量随着n的增大呈指数级增长，因此它的耗时也随之增加。而非递归函数的计算量是线性的，因此它的耗时相对较短。在实际开发中，应该尽可能使用非递归函数来计算斐波那契数列。