Go | 了解「遞迴函式」應用
💬 簡介
遞迴是程式設計中的一種重要技術，指的是一個函式在其執行過程中呼叫自己。Go 語言作為一種功能強大的程式語言，同樣支持遞迴的應用，讓開發者能夠以簡潔且高效的方式解決一些複雜的問題。
本文將介紹 Go 語言中的遞迴函式，並展示如何通過遞迴解決常見的問題，例如計算階乘、處理樹狀結構等。
圖片來源：Gophers
🔎 遞迴函式基礎
1️⃣ 什麼是遞迴？
遞迴是指一個函式在它的內部呼叫自己。在遞迴中，通常會設置一個基礎條件，當達到這個條件時，遞迴停止並返回結果。否則，遞迴會繼續進行，直到達到基礎條件。
2️⃣ 遞迴的基本結構
在遞迴函式中，通常有兩個部分：
- 基礎條件：當達到此條件時，遞迴停止。
- 遞迴步驟：函式呼叫自己來解決子問題。
3️⃣ 基本範例：計算階乘
階乘（Factorial）是遞迴的一個經典範例。階乘的定義是：
n! = n * (n-1)!，其中0! = 1範例：計算階乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15package main
import "fmt"
// 計算階乘的遞迴函式
func factorial(n int) int {
if n == 0 {
return 1 // 基礎條件
}
return n * factorial(n-1) // 遞迴步驟
}
func main() {
fmt.Println("5! =", factorial(5)) // 5! = 120
}輸出結果：
1
5! = 120
📝 在這個範例中，
factorial函式會不斷呼叫自己，直到n等於 0，並返回最終的階乘結果。
4️⃣ 遞迴的思考過程
當使用遞迴解決問題時，通常需要考慮兩個方面：
- 基礎條件：必須確保遞迴能夠終止，否則會導致無限遞迴。
- 遞迴步驟：每次遞迴呼叫必須處理一個比前一次更簡單的子問題，並逐漸逼近基礎條件。
🚀 應用場景
1️⃣ 處理樹狀結構
遞迴在處理樹狀結構（如文件系統、組織結構等）時非常有用。每個節點可以有多個子節點，遞迴可以讓我們方便地遍歷整個樹。
- 範例：遍歷樹狀結構輸出結果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29package main
import "fmt"
// 定義樹節點結構
type TreeNode struct {
Value int
Left *TreeNode
Right *TreeNode
}
// 遞迴遍歷樹的函式
func inorderTraversal(node *TreeNode) {
if node != nil {
inorderTraversal(node.Left) // 遞迴遍歷左子樹
fmt.Println(node.Value) // 輸出節點值
inorderTraversal(node.Right) // 遞迴遍歷右子樹
}
}
func main() {
root := &TreeNode{Value: 1}
root.Left = &TreeNode{Value: 2}
root.Right = &TreeNode{Value: 3}
root.Left.Left = &TreeNode{Value: 4}
root.Left.Right = &TreeNode{Value: 5}
inorderTraversal(root) // 輸出: 4 2 5 1 3
}1
2
3
4
54
2
5
1
3📝 在這個範例中，
inorderTraversal函式遞迴地遍歷整個二叉樹，並按照中序遍歷的順序輸出每個節點的值。
2️⃣ 解決分治問題
分治策略通常依賴遞迴來將一個大問題分解為多個小問題，並逐一解決它們。經典的分治演算法包括快速排序和合併排序。
- 範例：快速排序輸出結果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31package main
import "fmt"
// 快速排序函式
func quickSort(arr []int) []int {
if len(arr) < 2 {
return arr // 基礎條件，當陣列長度小於 2 時不再遞迴
}
pivot := arr[0]
left := []int{}
right := []int{}
for _, v := range arr[1:] {
if v < pivot {
left = append(left, v)
} else {
right = append(right, v)
}
}
left = quickSort(left) // 遞迴處理左邊子陣列
right = quickSort(right) // 遞迴處理右邊子陣列
return append(append(left, pivot), right...)
}
func main() {
arr := []int{9, 7, 5, 11, 12, 2, 14, 3, 10, 6}
fmt.Println("排序結果:", quickSort(arr))
}1
排序結果: [2 3 5 6 7 9 10 11 12 14]
📝 這個範例展示了快速排序演算法，其中遞迴的過程將陣列分割成兩部分，分別排序後合併結果。
3️⃣ 計算斐波那契數列
斐波那契數列是另一個常見的遞迴問題，其中每一項都是前兩項的和。這個問題可以通過遞迴來簡單實現。
- 範例：計算斐波那契數列輸出結果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17package main
import "fmt"
// 計算斐波那契數列的遞迴函式
func fibonacci(n int) int {
if n <= 1 {
return n // 基礎條件
}
return fibonacci(n-1) + fibonacci(n-2) // 遞迴步驟
}
func main() {
for i := 0; i < 10; i++ {
fmt.Printf("%d ", fibonacci(i))
}
}1
0 1 1 2 3 5 8 13 21 34
📝 這個範例展示了如何使用遞迴計算斐波那契數列中的每一項。
⚠️ 注意事項
📌 遞迴的效能問題
雖然遞迴能夠簡潔地解決許多問題，但過多的遞迴呼叫可能會導致堆疊溢位。特別是在處理大規模資料或深度遞迴時，必須小心使用。
📌 疊代 vs 遞迴
有些問題可以用疊代（loop）來解決，這樣能夠避免遞迴可能帶來的性能問題。在某些情況下，疊代方式可能更高效。
🎯 總結
- 遞迴是一種強大的程式設計技術，能夠幫助開發者簡潔地解決各類問題。
- Go 語言支援遞迴函式，可以用於計算階乘、處理樹狀結構、分治演算法等多種場景。
- 在使用遞迴時要小心處理基礎條件和遞迴步驟，避免無限遞迴或堆疊溢位。
掌握遞迴的基本概念和應用，能夠讓你的程式設計變得更加靈活且高效。
最後建議回顧一下 Go | 菜鳥教學 目錄，了解其章節內容。
註：以上參考了
Go
