函式可以調用函式本身
遞迴函式經典範例 ～ 階乘運算
package main
import "fmt"
func factorial(n int) int {
if n == 0 {
return 1
}
return n * factorial(n-1)
}
func main() {
fmt.Println(factorial(5)) // 120
}
數學的階乘（例如：5! = 5 * 4 * 3 * 2 * 1）可透過上述代碼實現，如果調用 factorial(10) 回傳值為 3628800。
上述代碼 line 17 當中，factorial 函式在其函式主體內調用了 factorial 自身，這是遞迴函式的語法特徵。由於 factorial 函式主體的開頭設有判斷式，factorial 函式不會因為反覆調用自身而陷入無窮迴圈。
函式執行上下文（Function Execution Context）
上述代碼中，每當遞迴函式被調用時，堆疊內就會產生新的函式執行上下文，
直到到達終止條件 (n == 0)，然後回傳計算結果。
Stack（堆疊）
堆疊是 FILO (First In Last Out) 的演算法。下列註解顯示上述代碼執行時，
堆疊內容納了五個 n * factorial(n-1)。
堆疊示意
/*
這裡是堆疊的出入口
return 1 * factorial(0) // 1 * 1 = 1
return 2 * factorial(1) // 2 * 1
return 3 * factorial(2) // 3 * 2 * 1
return 4 * factorial(3) // 4 * 3 * 2 * 1
return 5 * factorial(4) // 5 * 4 * 3 * 2 * 1
這裡是堆疊的底部
*/
上列註解中，line 5 以下的每個 factorial(n) 都會回傳上一行回傳的結果。
例如 line 7 是 4 * factorial(3)，相當於 4 乘以 line 6 的 3 * 2 * 1。於是當堆疊的最後一個上下文要離開堆疊時，回傳的結果就是 5! = 120。
最大公因數、費氏數列、河內塔
看到以上標題的三個名詞，你會想到什麼共通點？
其實除了階乘運算，遞迴函式也可應用於最大公因數 (GCD)、費波納契數列 (Fibonacci Sequence)、河內塔 (Hanoi Tower)。這三個應用場景也很常用於解釋何為遞迴。
此外，LeetCode 考題「Merge Two Sorted Lists」也可用遞迴函式解題。
迭代與遞迴（Iterative & Recursive）
舉凡遞迴函式可以解決的問題，也可用迭代法解決。以下函式係以迭代法實現階乘運算。
package main
import "fmt"
func factorial(n int) int {
result := 1
for i := 1; i <= n; i++ {
result *= i
}
return result
}
func main() {
fmt.Println(factorial(5)) // 120
}
迭代與遞迴的優缺點
綜合考量各種情況時，通常迭代與遞迴的優缺點如下：
- 代碼簡潔：迭代 < 遞迴（遞迴可讀性佳）
- 時間複雜度：迭代 < 遞迴（遞迴較費時）
- 空間複雜度：迭代 < 遞迴（堆疊佔用空間）