前言：遞歸函數是一種強大而又充滿魅力的編程技巧。它就像是一面神奇的鏡子，函數在其中能夠調用自身的倒影，從而以一種簡潔而優雅的方式解決許多復雜的問題。?
目錄
一、遞歸函數是啥玩意兒
二、遞歸函數的優缺點
優點
缺點
三、遞歸函數能干啥
四、遞歸函數咋優化
五、遞歸函數經典案例 - 漢諾塔問題
總結
一、遞歸函數是啥玩意兒
遞歸函數說白了，就是函數自己調用自己。不過，咱可不能讓函數這么一直調用下去沒完沒了，不然程序就 “跑偏” 了。所以得給它設個 “停止信號”，也就是終止條件。一到這個條件，函數就老實停下來，不再調自己啦，然后把之前算出來的結果一層一層地返回去。
舉個超簡單的例子，算階乘就特別適合用遞歸函數。階乘就是把一個正整數 n 和所有比它小的正整數都乘起來，像 5! = 5 × 4 × 3 × 2 × 1。咱用遞歸的思路想，其實就是 n! = n × (n - 1)! ，那咱就讓函數自己調自己，把問題越變越小，直到變成 1! = 1，這時候就讓函數停住返結果。
package mainimport "fmt"func factorial(n int) int {if n == 1 { // 咱的終止條件就這兒，要是 n 是 1，就返 1return 1}return n * factorial(n-1) // 這里函數就開始調自己啦，看不看懂？
}func main() {fmt.Println(factorial(5)) // 試一試，看看會不會返 120 呢
}看看，這代碼是不是超簡潔？就像把問題一層層剝開，找到最里面的核心，然后再一層層包回去，把結果算出來。
二、遞歸函數的優缺點
優點
-
代碼簡潔 ：遞歸函數能把復雜問題拆成小問題，代碼看著就清爽多了。比如算斐波那契數列（斐波那契數列就是從 0 和 1 開始，后面的數都是前兩個數的和），遞歸寫法就很簡單：
package mainimport "fmt"func fibonacci(n int) int {if n <= 1 {return n}return fibonacci(n-1) + fibonacci(n-2) // 自己調自己，把問題拆小
}func main() {fmt.Println(fibonacci(10)) // 算一算第 10 個斐波那契數
}缺點
-
性能問題 ：遞歸調用自己會搞出好多新的棧幀（棧幀就是函數調用時在內存里占的小窩），要是調用太多次，就會把棧給搞溢出，程序就直接 “撲街” 了。而且像斐波那契數列的簡單遞歸寫法，會算好多重復的東西，效率很低。
-
調試困難 ：遞歸函數調來調去，調試的時候得跟著好多層函數調用，搞起來有點麻煩。
三、遞歸函數能干啥
-
樹或圖的遍歷 ：比如遍歷文件系統里的目錄，遞歸地把每個文件夾和文件都瞅一遍：
package mainimport ("fmt""path/filepath"
)func traverseDir(path string) {entries, err := filepath.Glob(filepath.Join(path, "*"))if err != nil {fmt.Println("哎呀，出錯了：", err)return}for _, entry := range entries {if info, err := filepath.Stat(entry); err == nil && info.IsDir() {fmt.Println("哇，這是個文件夾：", entry)traverseDir(entry) // 遞歸遍歷子文件夾} else {fmt.Println("嘿，這是個文件：", entry)}}
}func main() {traverseDir("./testdir") // 假設當前目錄下有個叫 testdir 的文件夾
}-
深度優先搜索（DFS） ：在迷宮求解、八皇后這種問題里都能用上，像是在迷宮里一直往深處走，走不通了再回來換條路。
四、遞歸函數咋優化
-
記憶化 ：對于斐波那契數列，可以用記憶化避免重復算，搞個 “小本本” 把算過的結果記下來：
package mainimport "fmt"func fibonacci(n int, memo map[int]int) int {if val, exists := memo[n]; exists { // 先瞅瞅算過沒return val}if n <= 1 {memo[n] = n} else {memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)}return memo[n]
}func main() {memo := make(map[int]int)fmt.Println(fibonacci(10, memo)) // 算一算第 10 個斐波那契數
}-
尾遞歸優化 ：把遞歸調用放在函數的最后一步，有些編譯器會把它優化成循環，避免把棧搞崩。比如算階乘的尾遞歸寫法：
package mainimport "fmt"func factorial(n int, acc int) int {if n == 0 {return acc}return factorial(n-1, n*acc) // 尾遞歸調用
}func main() {fmt.Println(factorial(5, 1)) // 算一算 5 的階乘
}五、遞歸函數經典案例 - 漢諾塔問題
漢諾塔是個超經典的遞歸問題。有三根柱子 A、B、C，A 上面有 n 個盤子，按從大到小疊著。要求把所有盤子都移到 C 上，每次只能移一個，還不能把大的盤子放在小的上面。
package mainimport "fmt"func hanoi(n int, from, aux, to string) {if n == 1 {fmt.Printf("把盤子 1 從 %s 移到 %s\n", from, to)return}hanoi(n-1, from, to, aux) // 把 n-1 個盤子從 from 移到 auxfmt.Printf("把盤子 %d 從 %s 移到 %s\n", n, from, to) // 移最后一個盤子hanoi(n-1, aux, from, to) // 把 n-1 個盤子從 aux 移到 to
}func main() {hanoi(3, "A", "B", "C") // 算一算 3 個盤子咋移
}這段代碼把問題拆成把 n-1 個盤子移來移去的子問題，最后就解決了整個漢諾塔問題。
總結
遞歸函數就是這么個既厲害又有點小脾氣的工具。寶子們要是剛入門別怕，多寫寫多練練，理解了它的終止條件和調用過程，就能輕松用它搞定好多復雜問題。不過寫的時候得注意性能問題，要是函數調用太多，棧就不夠用了，必要時就用優化技巧。相信寶子們只要肯花時間，很快就能掌握遞歸函數的精髓，讓它變成自己編程路上的好幫手。
