#include  <iostream>

using namespace std;

//计算fibonacci数

//方法一：二分递归法，时间复杂度为O(2^n)，额外空间复杂度为常数

int RecursiveFibonacci(int n)

{

    return (n < ) ? n : RecursiveFibonacci(n - )+RecursiveFibonacci(n-);

}

//方法二：线性递归，时间复杂度为O(n),空间复杂度为O（n）

int LinearrecursionFibnoacci(int n,int& prev)//要用到引用，要不不可以！！！！

{

    if (n == )

    {

        prev = ;

        return ;

    }

    else

    {

        int prevPrev;

        prev = LinearrecursionFibnoacci(n - , prevPrev);

        return prevPrev + prev;

    }

}

//方法三：迭代法，时间复杂度为O(n),空间复杂度为常数

int IterationFibonacci(int n)

{

    int f = , g = ;

    while (n--)

    {

        g += f;

        f = g - f;

    }

    return g;

}

int main()

{

    int num_1,num_2,num_3;

    int f=;

    num_1 = RecursiveFibonacci();

    num_2 = LinearrecursionFibnoacci(, f);

    num_3 = IterationFibonacci();

    cout << num_1 << endl;

    cout << num_2 << endl;

    cout << num_3 << endl;

    return ;

}