費氏數列(Fibonacci Number)

讀資料結構，有時候會突然撞牆，每每已了解的知識，太久不用就會忘掉!
費氏數列(Fibonacci Number)是種很有趣的數列，
他的規則如下:








所以大致排列方式為

+-----+---+---+---+---+---+---+---+--------+
|  n  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ...... |
+-----+---+---+---+---+---+---+---+--------+
| Fib | 0 | 1 | 1 | 2 | 3 | 5 | 8 | ...... |
+-----+---+---+---+---+---+---+---+--------+

如果用樹狀圖會更容易了解





























使用遞迴的方式，可以得到費氏數列的值:

#include
int X(int n){
 if(n<=1) return n;
 else return X(n-1)+X(n-2);
}
int main(){
 printf("%d", X(6));
 getch();
 return 0;
}