數據結構與算法-遞歸
- 2020 年 4 月 6 日
- 筆記
1.什麼是遞歸
舉一個例子：大學軍訓的時候，一個隊伍，開頭的人A想知道這個隊伍一共有多少人，但是每個人只能通過旁邊的交流，那如何統計呢？
我們可以先找出最後一個人，A可以問旁邊的人B是否為最後一個人，B又問下一個人，如此類推，等到了最後一個人，再將號碼返回到第一個人A，每往前一個，號碼上就+1，第一個人A就知道這個隊伍有多少人了。
公式：g(n)=g(n-1)+1;g(1)=1
int AskNumberOfTeams(int n) { if(n == 1) { return 1; } return 1 + AskNumberOfTeams(n-1); }
遞歸可以看成一個嵌套的形式，一層層嵌套，執行相同的內容，到終止條件後往上返回結果。
遞歸有三個要素：1.判斷問題能否才分成小問題；2.每個小問題解決方案是否一致；3.是否有終止條件
2.簡單應用
斐波拉契數列
斐波拉契數列指的是1、1、2、3、5、8、13、21、34、55……。我們根據數列可以推導出，當前n位置的數值可以從前兩個數值和得到，公式為f(n)=f(n-1)+f(n-2)，f(1)=1與f(2)=1這兩個是遞歸的終止條件。
int CalFibonacci(int n) { if(n == 1 || n == 2) { return 1; } return CalFibonacci(n-1) + CalFibonacci(n - 2); }
階乘
階乘n!是小於等於n的正整數的積，並且0!=1，n!=1*2*3*4*……*(n-2)*(n-1)*n。根據公式可以拆分成n!=(n-1)!*n，且終止條件為0!=1。
int CalFactorial(int n) { if(n == 0) { return 1; } return CalFactorial(n - 1) * n; }
3.遞歸寫成非遞歸的形式
遞歸的形式都是可以寫成非遞歸的形式，用循環來替代遞歸。以上上面兩個應用可以改寫成：
斐波拉契數列
int CalFibonacciCycle(int n) { if(n == 1 || n == 2) { return 1; } int SecondValue = 1;//f(n-2) int FirstValue = 1;//f(n-1) int resultvalue;//f(n) for(int i=3; i<=n; i++) { resultvalue = FirstValue + SecondValue; SecondValue = FirstValue; FirstValue = resultvalue; } return resultvalue; }
階乘
int CalFactorialCycle(int n) { if(n == 0) { return 1; } int FirstValue = 1;//f(n-1) int resultvalue;//f(n) for(int i=1; i<=n; i++) { resultvalue = i * FirstValue; FirstValue = resultvalue; } return resultvalue; }
