如何使用遞歸，遞歸使用的技巧詳解
弄明白遞歸
什麼是遞歸
先來看下百度百科的定義：
程式調用自身的編程技巧稱為遞歸（ 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、青蛙跳台階問題
地址://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
}
總結
面對遞歸，我們不要試圖去弄明白每一步的調用邏輯，因為遞歸設計的層級是很深的，如果總想把每一步都想明白，就很容易被這個問題給繞進去了；
只想其中最簡單的兩層，找出遞推的關係；
因為子問題的不斷拆分，同時還需要找出退出的條件；
一個問題可以被拆分成一個個的小問題，並且拆分之後問題能夠變得更加簡單，同時被一直拆分的問題也有一個明確的終點，這種問題就很適合使用遞歸了。
參考
【遞歸】//baike.baidu.com/item/遞歸/1740695
【數據結構與演算法之美】//time.geekbang.org/column/intro/100017301
【手撕「漢諾塔演算法」之詳細圖解】//bbs.huaweicloud.com/blogs/270170
【如何使用遞歸，遞歸使用的技巧詳解】//boilingfrog.github.io/2022/10/27/遞歸在演算法中的使用/
