求斐波那契數列的第n個數（遞歸、非遞歸）

用遞歸的方式求斐波那契數列的第n個數。

用非遞歸的方式求斐波那契數列的第n個數。

定義：

     斐波那契數列指的是這樣一個數列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368

    特别指出：第0項是0，第1項是第一個1。

    這個數列從第2項開始，每一項都等于前兩項之和。

#include<stdio.h>
#include<stdlib.h>
#include<cmath>


int FibonacciRecursion(int a, int b, const int n)
{
 //存在n對應的一項可能超出 %d 所表示的整數範圍
 int count = n;
 if (0 == count)
  return a;
 else
 {
  if (a + b > 0)
   return FibonacciRecursion(b, a + b, --count);//傳入的a+b必須大于0
  else
   return -1;
 }
}

int FibonacciNonrecursionFormula(int const n)//非遞歸公式法(double與int轉換時有誤差)
{
 int count =(int) 1.0 / sqrt(5)*(pow((1.0 + sqrt(5)) / 2.0, n) - pow((1.0 - sqrt(5)) / 2, n));
 return count < 0 ? -1 : count;
}

int FibonacciNonrecursion(int const n)//非遞歸非公式法
{
 int count = n;
 int a = 0;
 int b = 1;
 int tmp = a;
 if (0 == n)
  return a;
 if (1 == n)
  return b;
 else
 {
  while (count--)
  {
   tmp = a;
   a = b;
   b = a + tmp;
   if (a < 0)
    return -1;
  }
  return a;
 }
}
int main()
{
 int n = 0;
 while (n++<88)
 {
  if (FibonacciRecursion(0, 1, n) != FibonacciNonrecursionFormula(n) || FibonacciNonrecursion(n) != FibonacciNonrecursionFormula(n))
  {
   printf("Fibonacci 數列第 %d 項為：%d - %d\n", n, FibonacciRecursion(0, 1, n), FibonacciNonrecursionFormula(n));
   printf("              第 %d 項為：%d\n", n, FibonacciNonrecursion(n));
  }
 }

 printf("%d\n", 2836311903);//45項+46項 < 2836311903  是以在46以後大于0x7fffffff
 system("pause");
 return 0;
}