斐波那契的递归和迭代方法实现和性能对比

c语言实现

#include<stdio.h>  
#include<time.h>
#include <windows.h>
#pragma warning( disable : 4996)

typedef unsigned long long int longint;
//这个是为longlong类型整形的无符号的类型起个别名为longint，
//主要是为了输出更大的数，主要是为了输出更大斐波那契数的时候使用，可以不用管这个
longint diedai(int n);
void digui_show(int n);
void diedai_show(int n);
longint digui(int n);

int main()
{
    int n = 40;
    //声明四个个时间类型的变量,主要是比较迭代和递归使用的时间
    DWORD diedai_start, diedai_stop, digui_start, digui_stop;
    printf("########迭代方法##########\n");
    diedai_start = GetTickCount();
    //调用迭代方法
    diedai_show(n);
    diedai_stop = GetTickCount();
    longint l = diedai_stop - diedai_start;
    printf("\n迭代使用输出%d个数使用的时间为: %lld ms\n",n, l);

    printf("########递归方法##########\n");
    digui_start = GetTickCount();
    //调用递归方法
    digui_show(n);
    digui_stop = GetTickCount();
    longint l2 = digui_stop - digui_start;
    printf("\n递归使用输出%d个数使用的时间为: %lld ms\n", n, l2);
    system("pause");
    return 0;
}

void diedai_show(int n) {
    //这个函数是通过for循环调用迭代的方法输出N个斐波那契的数
    for (int i = 1; i <= n; i++) {
        if (i % 4 == 0 && i>1)printf("\n");
        printf("%8lld\t\t", diedai(i));
    }
}

void digui_show(int n) {
    //这个函数是通过for循环调用递归的方法输出N个斐波那契的数
    for (int i = 1; i <= n; i++) {
        if (i % 4 == 0 && i > 1)printf("\n");
        printf("%8lld\t\t", digui(i));
    }
}

longint diedai(int n){
    //这个函数是通过迭代的方法返回第N个斐波那契的数
    longint i = 0, x1 = 0, x2 = 1, x3 = 0;
    if (n < 2)return 1;
    for (i = 2; i <= n; i++)
    {
        /*这是实现叠加也是迭代的for循环，n是第几个斐波那契的数，然后就迭代n次*/
        x3 = x1 + x2;
        x1 = x2;
        x2 = x3;
    }
    return x3;
}

longint digui(int n) {
    //这个函数是通过递归的方法返回第N个斐波那契的数
    if (n ==1||n==2)
    {
        return 1;
    }
    return digui(n - 2) + digui(n - 1);

}

两种方法的性能对比还是很明显的，所以在使用斐波那契的一定要选择合适的方式