斐波那契数列

解题思路

公式：f(0) = 0, f(1) = 1, f(2)=1, f(n)=f(n-1)+f(n-2)

代码

递归

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

非递归

int fibona(int n)
{
      if(n==0)
         retrurn 0;
      if(n==1 || n==2)
         return 1;
      int a = 1;
      int b = 1;
      int num = 0;
      for(int i=3;i<=n;i++)
      {
          num = a+b;
         a = b;
         b=num;
      }
      return num;
}