一、定義簡述

  • 遞歸：函數在執行過程中調用自身，通過不斷縮小問題規模，最終達到一個“基準條件”後返回。
  • 迭代：通過循環結構（如 for、while）重複執行一段代碼，直到滿足退出條件。

二、優缺點對比

維度

遞歸（Recursion）

迭代（Iteration）

代碼可讀性

✅ 通常更簡潔、直觀，尤其適合具有自相似結構的問題（如樹、圖、分治）

❌ 有時邏輯較複雜，需要手動維護狀態

執行效率

❌ 函數調用有開銷（壓棧/出棧），時間與空間複雜度通常更高

✅ 效率高，無額外函數調用開銷

內存消耗

❌ 每次調用都會佔用棧空間，深度過大易導致 StackOverflowError

✅ 僅使用常量或少量變量，內存佔用低

適用場景

✅ 樹遍歷、回溯、分治、數學定義（階乘、斐波那契）、漢諾塔等

✅ 簡單計數、累加、數組遍歷等線性任務

調試難度

❌ 調用棧深，調試和追蹤較困難

✅ 狀態清晰，易於單步調試

尾遞歸優化支持

⚠️ Java、Python 等主流語言不支持自動尾遞歸優化

（Scala、Erlang、Haskell 等函數式語言支持）

不適用

三、實例對比：計算階乘

遞歸實現

public static int factorialRec(int n) {
    if (n <= 1) return 1;
    return n * factorialRec(n - 1);
}

迭代實現

public static int factorialIter(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

✅ 結論：

  • 遞歸代碼更貼近數學定義，易理解；
  • 迭代效率更高，且不會棧溢出。

四、何時選擇遞歸？何時選擇迭代？

優先使用 遞歸 的情況：

  • 問題天然具有遞歸結構（如二叉樹、圖的深度優先搜索）
  • 使用回溯算法（如全排列、N皇后）
  • 分治策略（如歸併排序、快速排序）
  • 代碼簡潔性比性能更重要（如原型開發、教學演示）

優先使用 迭代 的情況：

  • 問題可通過簡單循環解決（如求和、查找、遍歷數組）
  • 對性能或內存有嚴格要求
  • 遞歸深度不可控（如處理大規模輸入）
  • 目標平台不支持深層遞歸（如嵌入式系統）

五、補充：遞歸轉迭代的技巧

很多遞歸算法可以通過顯式使用棧（Stack） 轉換為迭代形式。例如：

  • 二叉樹的前序遍歷（遞歸 → 用 Stack 模擬）
  • DFS（深度優先搜索）可用 Stack 實現
  • 尾遞歸可直接改寫為 while 循環

💡 經驗法則：如果遞歸只有一次自我調用（如階乘），通常容易轉為迭代；如果有多個分支（如斐波那契、樹遍歷），轉換會更復雜。