問：何為遞回函式?
說人話：自己呼叫自己的函式就叫遞回函式，
遞回函式寫法
實作一個遞回函式，我將其概括為是一個“推卸責任”的程序，分為3個步驟：
- 列出方法簽名：明確該函式/方法的輸入輸出，由此寫出它的方法簽名（method’s signature），方法簽名包括修飾符，回傳值型別，方法名和引數串列，
- 完成邊界情況（base case，也稱基準情況）：即找到“替罪羊”，因為不停地把問題往下級推卸，最后總得有人出來背鍋，
- 完成遞回情況（recursive case）：即完成責任推卸鏈，把問題從第\(n\)層推卸到第\(n - 1\)層，
我們將用求階乘的例子來詳細解釋這3個步驟，
列出方法簽名
首先，明確輸入輸出：我們希望只要給該方法/函式一個整數，就能回傳它的階乘，那么該遞回方法的方法簽名即為如下：
public int factorial(int n){};
這樣我們就完成了實作遞回函式的第1個步驟了，
完成邊界情況
很顯然階乘的邊界情況就是求1的階乘，它沒有理由再把計算的責任推卸給任何人了，因為它自己就能直接得出計算結果1，所以求1的階乘就是我們要找的那只“替罪羊”，
因此，基準情況即為如下：
if (n == 1) return n;
完成遞回情況
提前找好了“替罪羊”，接下來我們只需要把“責任推卸鏈”完成，讓責任一級一級最終推卸到替罪羊身上，就可以大功告成！
而要完成這條“責任推卸鏈”，其實就是列出關于原問題和子問題的數學等價關系式，
對于求階乘而言，原問題和子問題的等價關系式為：\(n! = n \times (n - 1)!\)，這樣，就將問題從第\(n\)層成功地轉移到了第\(n-1\)層，
那么對應的代碼實作即為如下：
else return n * factorial(n - 1);
綜合以上3個步驟，完整版的實作階乘的遞回函式即為：
/** Returns n factorial. */
public int factorial(int n) {
// Base case
if (n == 1)
return n;
// Recursive case
else
return n * factorial(n - 1);
}
在這個遞回函式里，我們定義了遞回情況來一步步簡化問題，也定義邊界情況來計算出最終的邊界值，所以我們大可放心地呼叫該函式，讓它自行去解決問題，
看到這里，相信你已經掌握了遞回函式的寫法，可以看出，寫出一個遞回函式并沒有那么容易，而我們可不希望當我們絞盡腦汁憋出一個遞回函式后，卻換來老板一句“多此一舉，凈瞎折騰”，
那要避免這種情況，我們得先弄清楚一個前提：什么時候派上遞回最為合適？
什么時候應用遞回
我們先來談談遞回的缺點：
- 對空間消耗大，容易導致堆疊溢位
遞回是呼叫自身的函式，而函式的每次呼叫都會在堆疊中產生呼叫幀（call frame, 用來保存內部變數、回傳點等資訊），可堆疊的空間是有限的，沒法一次同時保存過多的呼叫幀，所以如果呼叫的次數多了就容易導致堆疊溢位，對空間消耗大， - 對時間消耗大，導致運行效率低
首先，往堆疊中壓入和彈出資料需要時間；此外，遞回中經常會產生很多重復計算，例如在斐波那契數列的遞回實作中，當n = 5時，需要計算一遍的fibonacci(3)，推導到n = 4時，又需要計算一遍fibonacci(3)，也就是說求一個5的階乘需要計算兩遍的fibonacci(3)，所以說時間效率低，
（可以利用一個陣列或哈希map來保存已計算出的結果來避免重復計算）
而遞回主要是用于以下兩種情況：
- 資料結構本身就是按遞回的形式定義的，
例如斐波那契數列、n的階乘、二叉樹的遍歷、圖的搜索等，這種情況下，以其人之道還治其人之身當然是很直觀了當的做法， - 問題能以同樣的解法逐級減小問題規模
例如分治演算法、回溯演算法等，它們能用同樣的解法去一步步減小問題規模，所以用遞回實作起來就很方便，
所以，除非是以上兩種情況，否則盡量避免使用遞回，以避免對空間和時間產生大的消耗，（P.S. 把浪費的這些功夫拿去打王者榮耀它不香嗎...）
總結
遞回函式是自己呼叫自己的函式，通過列出方法簽名，完成基準情況和遞回情況即可完成一個遞回函式，但是用遞回實作通常會對時間和空間產生大的消耗，因此除非資料結構本身就是按遞回的形式定義或是問題能以同樣的解法逐級減小問題規模，否則應盡量避免使用遞回，
參考
- https://mp.weixin.qq.com/s/tqGKHZzSyDBgEp-oWsOztQ
創作不易，點個贊再走叭～
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/236997.html
標籤：其他