如何使用遞迴，遞迴使用的技巧詳解
弄明白遞迴
什麼是遞迴
先來看下百度百科的定義：
程式呼叫自身的程式設計技巧稱為遞迴（ recursion）。遞迴作為一種演演算法在程式設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的程式碼量。遞迴的能力在於用有限的語句來定義物件的無限集合。一般來說，遞迴需要有邊界條件、遞迴前進段和遞迴返回段。當邊界條件不滿足時，遞迴前進；當邊界條件滿足時，遞迴返回。
簡單總結下來遞迴需要滿足下面三個條件
1、一個問題可以分解為幾個問題的解；
- 什麼是子問題呢？就是資料規模更小的問題。
2、該問題分解之後的子問題，除了資料規模不同，求解思路完全一樣；
3、存在遞迴終止條件。
拆解子問題的時候，我們會把問題拆分成子問題，然後在把子問題拆分成子子問題的過程，依次類推，這就需要一定有個終止條件，不能出現無限迴圈的錯誤情況出現。
什麼問題適合使用遞迴解決？
一個問題可以被拆分成一個個的小問題，並且拆分之後問題能夠變得更加簡單，同時被一直拆分的問題也有一個明確的終點，這時候就可以考慮使用遞迴了。
編寫遞迴的技巧
關鍵的技巧主要是
1、找出遞推公式，就是如何將大問題拆分成小問題的規律；
2、因為有子問題的拆分迴圈，需要找出終止退出的條件；
3、還有一個比較關鍵的點，因為遞迴涉及到的層級很深，不用想一層層的呼叫關係，不要試圖用人腦去分解遞迴的每個步驟，基於現有的條件找出遞推的公式。
面對遞迴，我們總是想弄明白每一步的呼叫邏輯，總想把遞迴平鋪展開，腦子裡就會迴圈，一層一層往下調，然後再一層一層返回，試圖想搞清楚計算機每一步都是怎麼執行的，這樣很容易就會被設個問題繞進去了。
遞迴的缺點
遞迴呼叫，佔用空間大；
遞迴太深，容易發生堆疊溢位；
可能存在重複計算。
來幾個栗子
來幾個遞迴演演算法的經典栗子，來了加深下對遞迴演演算法的瞭解
1、斐波那契數列
斐波那契數列是遞迴中一道非常經典的題目
斐波那契數列是指這樣一些列數列：：1、1、2、3、5、8、13、21、...... 這個數列的規律就是從第三項開始的每一項都等於前面兩項的和，例如 3+5=8，,5+8=13。
題目要求：輸入序號 N，輸出對應的斐波那契數？
用函數表示就是F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)。
下面使用遞迴實現下
func f(n int) int {
if n < 3 {
return 1
}
return f(n-1) + f(n-2)
}
其中 F(n)=F(n-1)+F(n-2) 就是這道題目的遞推公式
if n < 3 {
return 1
}
就是終止退出的條件。
上面就是當傳入的資料為 5，函數的遞迴呼叫過程
2、兔子繁衍問題
假設一對剛出生的小兔一個月後就能長成大兔，再過一個月就能生下一對小兔，並且此後每個月都生一對小兔，一年內沒有發生死亡，問：一對剛出生的兔子，一年內繁殖成多少對兔子?
這也是一道經典的斐波那契數列問題，首先來分析下這個兔子的資料
通過分析可知，這就是典型的斐波那契數列問題 1、1、2、3、5、8、13、21
func f(n int) int {
if n < 3 {
return 1
}
return f(n-1) + f(n-2)
}
3、青蛙跳臺階問題
地址:https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
一隻青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個 n 級的臺階總共有多少種跳法。
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。
範例 1：
輸入：n = 2
輸出：2
範例 2：
輸入：n = 7
輸出：21
範例 3：
輸入：n = 0
輸出：1
解題思路：
首先找到遞推公式，因為每次能夠走 1 步或者 2 步。
所以n個臺階的走法就等於先走 1 階後，n-1 個臺階的走法 加上先走 2 階後，n-2 個臺階的走法。用公式表示就是：f(n)=f(n-1)+f(n-2)
再來看下終止條件
f(1) = 1
f(2) = 2
同時最終遞迴的數位肯定是落到 1 和 2 上了，那就可以設定最後的 1 和 2 為最終終止的條件
func f(n int) int {
if n < 1 {
return 1
}
if n < 2 {
return 2
}
return f(n-1) + f(n-2)
}
4、漢諾塔問題
漢諾塔問題的描述：
假設有 A、B、C 三根柱子。其中在 A 柱子上，從下往上有 N 個從大到小疊放的盤子。我們的目標是，希望用盡可能少的移動次數，把所有的盤子由 A 柱移動到 C 柱。過程中，每次只能移動一個盤子，且在任何時候，大盤子都不可以在小盤子上面。
解題思路：
我們使用遞迴的思路去思考，首先找出遞推的公式
我們把一個 N 層漢諾塔從 A 搬到 C，我們假定只有兩層，首先把 N-1 層搬到 B,然後把下面的第 N 層搬到 C，然後再把 N-1 層從 B 搬到 C 。
如果存在多層，那我們就假定 N-1 層已經排好序了，只搬第 N 層，這樣依次遞迴下去。
終止條件：
當只剩下最後一個的時候，我們只需要搬動一次就行了
var count int = 0
func main() {
beadNum := 5 // This is the initial number of beads
hanoi(beadNum, "A", "B", "C")
fmt.Println(count)
}
func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) {
if beadNum == 1 {
// 最後一個了，可以結束了
move(beadNum, pillarA, pillarC)
} else {
// Step 2: 將 N-1 層從 A 移動到 B
hanoi(beadNum-1, pillarA, pillarC, pillarB)
// Step 2: 將第 N 層從 A 移動到 C
move(beadNum, pillarA, pillarC)
// Step 3: 將 B 中的 N-1 層移動到 C
hanoi(beadNum-1, pillarB, pillarA, pillarC)
}
}
func move(beadNum int, pillarFrom string, pillarTo string) {
count += 1
}
5、二元樹的遍歷
這裡使用遞回來實現下，二元樹的前序，中序，和後續的遍歷
前序遍歷
前序的就是先當前節點，然後左節點，然後右節點，這就是一層的遞迴
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func preorderTraversal(root *TreeNode) []int {
var res []int
if root != nil {
res = append(res, root.Val)
res = append(res, preorderTraversal(root.Left)...)
res = append(res, preorderTraversal(root.Right)...)
}
return res
}
中序遍歷
中序遍歷的順序為：先遍歷左節點，然後遍歷根節點，最後遍歷右節點
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func inorderTraversal(root *TreeNode) []int {
var res []int
if root != nil {
res = append(res, inorderTraversal(root.Left)...)
res = append(res, root.Val)
res = append(res, inorderTraversal(root.Right)...)
}
return res
}
後序遍歷
後序遍歷的順序為：先遍歷左節點，然後遍歷右節點，最後遍歷根節點
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func recursionPostorderTraversal(root *TreeNode) []int {
var res []int
if root != nil {
res = append(res, recursionPostorderTraversal(root.Left)...)
res = append(res, recursionPostorderTraversal(root.Right)...)
res = append(res, root.Val)
}
return res
}
總結
面對遞迴，我們不要試圖去弄明白每一步的呼叫邏輯，因為遞迴設計的層級是很深的，如果總想把每一步都想明白，就很容易被這個問題給繞進去了；
只想其中最簡單的兩層，找出遞推的關係；
因為子問題的不斷拆分，同時還需要找出退出的條件；
一個問題可以被拆分成一個個的小問題，並且拆分之後問題能夠變得更加簡單，同時被一直拆分的問題也有一個明確的終點，這種問題就很適合使用遞迴了。
參考
【遞迴】https://baike.baidu.com/item/遞迴/1740695
【資料結構與演演算法之美】https://time.geekbang.org/column/intro/100017301
【手撕「漢諾塔演演算法」之詳細圖解】https://bbs.huaweicloud.com/blogs/270170
【如何使用遞迴，遞迴使用的技巧詳解】https://boilingfrog.github.io/2022/10/27/遞迴在演演算法中的使用/