Fibonacci數列

無窮數列1,1,2,3,5,8,13,21,34,55，···，稱為Fibonacci數列。它可以遞迴的定義為

1 n=0

F(n)= 1 n=1

F(n-1)+F(n-2) n>1

第n個Fibonacci數可遞迴地計算如下：

int Fibonacci ( intn)

{

If(n

ReturnFibonacci(n-1)+Fibonacci(n-2);

}

1+T(n-1)+T(n-2) n>1

Tn=

0 n

時間複雜度為指數時間O(kn)

非遞迴計算如下：

Int Fibonacci(int n)

{

If(n

else{

int a=b=1;

for(int i=0;i