一、概念
1.遞歸
遞歸是指一個函數在其定義中直接或間接調用自身的編程方法 。簡單來說，就是函數自己調用自己。遞歸主要用于將復雜的問題分解為較小的、相同類型的子問題，通過不斷縮小問題的規模，直到遇到一個最簡單、最基礎的情況（基本情況），從而停止遞歸。
遞歸算法有兩個過程，一是遞推過程，二是回歸的過程。
2.循環
循環是計算機科學運算領域的用語，也是一種常見的控制流程。循環是一段在程序中只出現一次，但可能會連續運行多次的代碼。循環中的代碼會運行特定的次數，或者是運行到特定條件成立時結束循環，或者是針對某一集合中的所有項目都運行一次。
二、執行過程
1.遞歸
在支持自調用的編程語言中，遞歸可以通過簡單的函數調用來完成，如計算階乘的程序在數學上可以定義為：
遞歸程序執行過程可分解為下圖
2.循環
循環開始前需要初始化變量，然后進入表達式做判斷，判斷為true，執行循環體，判斷為false則退出循環，輸出結果
循環程序執行過程可分解為下圖：
三、代碼示例
1.go語言代碼示例
package mainimport ("fmt""time"
)// 直接遞歸調用，求n的階乘
// 參數:
//
// n - 一個正整數，表示需要計算階乘的數字。
//
// 返回值:
//
// result - n 的階乘結果。
func recursion(n int) (result int) {if n >= 1 {// 直接遞歸調用函數result = n * recursion(n-1)return result}return 1
}// loop 計算給定數字的階乘。
// 參數:
//
// n - 一個正整數，表示需要計算階乘的數字。
//
// 返回值:
//
// result - n 的階乘結果。
func loop(n int) (result int) {// 當n < 0時，程序panic退出if n <= 0 {panic("Input must be a non-negative integer")}// 初始化 y 為 1，作為階乘計算的起始值。y := 1// 從 1 循環到 n，逐步計算階乘。for i := 1; i <= n; i++ {// 在每次循環中，將當前數字 i 與 y 相乘，累積階乘結果。y *= i}// 返回計算得到的階乘結果。return y
}func main() {// 初始化變量x為10，用于后續的遞歸和循環計算。x := 5// 開始遞歸計算，并記錄開始時間。startRecurison := time.Now()// 打印遞歸計算的開始時間、結果以及花費的時間。fmt.Printf("recurison start time:%v, result:%d\n", startRecurison, recursion(x))fmt.Println("elapse time:", time.Since(startRecurison))// 開始循環計算，并記錄開始時間。startLoop := time.Now()// 打印循環計算的開始時間、結果以及花費的時間。fmt.Printf("loop start time:%v, result:%d\n", startLoop, loop(x))fmt.Println("elapse time:", time.Since(startLoop))// 比較遞歸和循環的執行時間，判斷哪個更快。if time.Since(startRecurison) > time.Since(startLoop) {fmt.Println("loop algorithm is faster")} else {fmt.Println("recursion algorithm is faster")}
}
2.查看執行結果
最終比較結果：循環算法的執行效率更好，速度更快
PS D:\Project\GoWorkSpace\DataStructure\0408> go run .\Recursion.go
recurison start time:2025-04-09 10:49:17.117547 +0800 CST m=+0.005692801, result:120
elapse time: 2.9766ms
loop start time:2025-04-09 10:49:17.1205236 +0800 CST m=+0.008669401, result:120
elapse time: 533.2μs
loop algorithm is faster
四、總結
1.遞歸和循環的區別
1.1內存占用
遞歸：每次調用都會在調用棧中保存當前狀態，深度遞歸可能導致棧溢出（如 n=10000 時計算階乘）。
循環：通常只占用常量內存（如幾個變量）。
1.2效率
遞歸：函數調用需要額外開銷（保存上下文、參數傳遞等），但某些語言支持尾遞歸優化（如 Scheme），可減少開銷。
循環：通常更高效，無函數調用開銷。
1.3可讀性
遞歸：更符合分治、樹遍歷等問題的數學定義（如斐波那契數列、漢諾塔）。
循環：適合簡單重復任務（如遍歷數組）。
1.4典型場景
遞歸：分治算法（快速排序）、樹/圖遍歷（DFS）、動態規劃問題。
循環：線性操作（如求和、遍歷）、需要嚴格控制資源時。
1.5轉換與限制
- 相互轉換
任何遞歸問題都可以用循環（+棧結構）實現，反之亦然，但代碼復雜度可能變化。 - 限制
遞歸：受編程語言的調用棧深度限制。
循環：需手動管理狀態，復雜邏輯可能使代碼臃腫。
1.6總結表格
| 遞歸 | 循環 | |
|---|---|---|
| 實現方式 | 函數自我調用 | 顯式迭代（for/while） |
| 內存占用 | 高（棧幀累積） | 低（常量空間） |
| 性能 | 可能因調用開銷較慢 | 通常更高效 |
| 可讀性 | 適合分治、樹結構問題 | 簡單直觀 |
| 適用場景 | 分治、回溯、數學遞歸問題 | 線性操作、資源敏感任務 |
2.場景選擇
用遞歸：問題本身是遞歸結構、代碼簡潔性優先（如樹的遍歷）
用循環：追求性能、處理大數據量、避免棧溢出風險。
概念補充
遞歸展開：指通過逐步展示遞歸函數的調用過程，將遞歸的每一層執行細節明確呈現出來，以直觀理解遞歸如何分解問題、傳遞參數、返回結果。這一過程常用于分析遞歸邏輯、調試代碼或手動模擬遞歸行為。
如果出現遞歸算法棧溢出，用循環算法優化也是一種方法
如有疏漏，歡迎評論區留言
