您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> ASP.NET 基礎 >> ASP.NET 基礎

C# 遞歸函數完整指南：原理、經典案例、效能陷阱與最佳實踐

編輯：ASP.NET 基礎

什麼是遞歸？

方法呼叫自身即為遞歸。兩大特徵：
1. 基底條件：終止遞歸的判斷邏輯。
2. 遞歸步驟：將問題縮小並傳遞新參數呼叫自身。
C# 早期僅有方法，.NET 3.5 引入 Lambda 才出現匿名函數，故慣稱「遞歸方法」。

為何使用遞歸？

「任何可用迴圈解決的問題皆可用遞歸表示」（Ellis Horowitz）。遞歸適合處理結構遞歸的問題：樹狀結構、圖遍歷、分治演算法、回溯法。但頻繁使用呼叫堆疊，可能導致 StackOverflowException 與效能損耗。

經典案例解析

1. 階乘

// 迭代版（推薦）
public long Factorial(int n)
{
    if (n == 0) return 1;
    long v = 1;
    for (int i = n; i > 0; i--) v *= i;
    return v;
}

// 遞歸版（教學用）
public long FactorialRec(int n)
{
    if (n == 0) return 1;          // 基底條件
    return n * FactorialRec(n - 1); // 遞歸步驟
}

遞歸版雖簡潔，但 n > 20 即溢位，且堆疊深度為 O(n)。

2. 費波納契數列

// 迭代版 O(n) 時間、O(1) 空間
public long Fib(int n)
{
    if (n < 2) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
    return b;
}

// 遞歸版 O(2^n) 時間、O(n) 堆疊 —— 極差效能
public long FibRec(int n)
{
    if (n == 0 || n == 1) return n;
    return FibRec(n - 2) + FibRec(n - 1); // 大量重複計算
}

遞歸版為教科書級「遞歸效能反面教材」，實務必用迭代或記憶化。

3. 布林組合列舉

n 個布林變數產生 2^n 種組合，遞歸極適合：

public void BooleanCompositions(int count)
{
    BooleanCompositions(count - 1, "true");
    BooleanCompositions(count - 1, "false");
}
private void BooleanCompositions(int counter, string partial)
{
    if (counter <= 0) Console.WriteLine(partial);
    else
    {
        BooleanCompositions(counter - 1, partial + ", true");
        BooleanCompositions(counter - 1, partial + ", false");
    }
}

4. 取得最內層 InnerException

public Exception GetInnerException(Exception ex)
{
    return ex.InnerException == null ? ex : GetInnerException(ex.InnerException);
}
// 等價於
public Exception GetInnerException(Exception ex)
{
    if (ex.InnerException == null) return ex;
    return GetInnerException(ex.InnerException);
}

遞歸完美契合「巢狀結構同質操作」場景。

5. 遞歸搜尋檔案

private readonly List<string> _results = new();
private readonly Dictionary<string, string> _errors = new();

public void SearchFiles(string path)
{
    try
    {
        foreach (var file in Directory.GetFiles(path)) _results.Add(file);
        foreach (var dir in Directory.GetDirectories(path)) SearchFiles(dir); // 遞歸
    }
    catch (Exception ex) { _errors[path] = ex.Message; }
}

目錄樹天然遞歸結構，無需額外基底條件（無子目錄時迴圈自然結束）。

效能陷阱與優化策略

問題	原因	對策
堆疊溢位	遞歸深度超過 CLR 預設 1MB 堆疊	改迭代、增加尾端遞歸優化（C# 不支援）、使用 `Stack<T>` 手動模擬
重複計算	子問題重疊（如 Fib）	記憶化、動態規劃、迭代
記憶體壓力	大量建立堆疊框架	避免在遞歸中配置大型物件、使用 `yield return` 延遲執行