遞迴函式 (三) - 費氏數列

方浩葦

費氏數列 - 維基百科

費氏數列規則如下：
第n項 = 第 n-1 項  + 第 n-2 項

即整個費式數列為：
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377...

試完成一程式，能推算費氏數列至指定項次：

1. #include<iostream>
   
2. #include<cstdlib>
   
3. using namespace std;
   
4. int fai(int n)
   
5. {
   
6.     if(n<2)    //邊界條件
   
7.         return n;
   
8.     else
   
9.         return fai(n-2)+fai(n-1);
   
10. }
    
11. /*
    
12. fai(5)
    
13. =fai(3)+fai(4)
    
14. =fai(1)+fai(2)+fai(2)+fai(3)
    
15. =1+fai(0)+fai(1)+fai(0)+fai(1)+fai(1)+fai(2)
    
16. =1+0+1+0+1+1+fai(0)+fai(1)
    
17. =1+0+1+0+1+1+0+1
    
18. =5
    
19. */
    
20. int main()
    
21. {
    
22.     int n;
    
23.     cout<<"請問要推算費氏數列到第幾項次? ";
    
24.     cin>>n;
    
25.     for(int i=0; i<=n; i++)
    
26.         cout<<fai(i)<<" ";
    
27.     cout<<endl;
    
28.     system("pause");
    
29.     return 0;
    
30. }

複製代碼