尾遞歸與 Continuation：從棧溢出到 CPS 程式設計風格

遞歸是優雅但危險的工具。當遞歸深度超過線程棧大小（Windows 預設 1MB）時，將拋出 StackOverflowException。本文深入剖析尾遞歸與Continuation Passing Style (CPS)如何解決此問題，並透過鏈表長度、費波納契數列、二叉樹遍歷等經典案例，展示從普通遞歸到尾遞歸、再到 CPS 的思維演進。

普通遞歸與棧溢出風險

計算單向鏈表長度的普通遞歸：

public static int GetLengthRecursively(Node head) {
    if (head == null) return 0;
    return GetLengthRecursively(head.Next) + 1; // 遞歸返回後仍需執行 "+1"
}

每次調用在棧上保存參數、返回地址等資訊，深度過大導致棧溢出。

尾遞歸：消除棧幀堆疊

關鍵在於「遞歸調用是方法的最後一個操作」，且所有中間狀態通過參數（累加器 acc）傳遞：

public static int GetLengthTailRecursively(Node head, int acc) {
    if (head == null) return acc;
    return GetLengthTailRecursively(head.Next, acc + 1); // 尾調用，無後續操作
}
// 調用：GetLengthTailRecursively(head, 0)

編譯器/運行時若支援尾調用優化 (TCO)，可重用當前棧幀，實現 O(1) 棧空間。註：C# 編譯器與 JIT 目前不支援 TCO，尾遞歸在 C# 中仍會棧溢出，僅具教學意義。

費波納契數列的尾遞歸轉換

傳統遞歸為雙重遞歸，效率極低（指數級）。尾遞歸版本需兩個累加器維護前兩項：

public static int FibonacciTailRecursively(int n, int acc1, int acc2) {
    if (n == 0) return acc1;
    return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}
// 調用：FibonacciTailRecursively(10, 0, 1)

Continuation Passing Style (CPS)：解決多重遞歸難題

某些演算法（如二叉樹先序遍歷）天然包含多個遞歸調用，無法直接轉為尾遞歸。CPS 將「後續計算」封裝為委派（Continuation）傳遞，強行構造尾調用形式。

階乘的 CPS 改寫

public static int FactorialContinuation(int n, Func<int, int> continuation) {
    if (n == 0) return continuation(1);
    return FactorialContinuation(n - 1, r => continuation(n * r));
}
// 調用：FactorialContinuation(10, x => x)

二叉樹先序遍歷：CPS 必用場景

public static void PreOrderTraversal(TreeNode root, Action<TreeNode> continuation) {
    if (root == null) { continuation(null); return; }
    Console.WriteLine(root.Value);
    // 左子樹完成後，以 continuation 包裝右子樹遍歷
    PreOrderTraversal(root.Left, left => PreOrderTraversal(root.Right, right => continuation(right)));
}

此處必須使用 CPS，因為順序遍歷左、右子樹構成兩個遞歸分支，無法自然尾調用。

CPS 改進：累加器與 Continuation 結合

純 CPS 會產生大量匿名委派物件（托管堆分配），影響效能。引入累加器可減少閉包創建：

// 改進前：每層創建 2 個委派
public static int GetSize(TreeNode root, Func<int, int> continuation) {
    if (root == null) return continuation(0);
    return GetSize(root.Left, leftSize => GetSize(root.Right, rightSize => continuation(leftSize + rightSize + 1)));
}

// 改進後：引入 acc，僅創建 1 個委派/層
public static int GetSize2(TreeNode root, int acc, Func<int, int> continuation) {
    if (root == null) return continuation(acc);
    return GetSize2(root.Left, acc, accLeftSize => GetSize2(root.Right, accLeftSize + 1, continuation));
}
// 調用：GetSize2(root, 0, x => x)

總結與啟示

• 命令式語言：通常用迴圈替代遞歸，避免棧溢出。
• 函數式語言：無迴圈構造，尾遞歸與 CPS 是實現迭代的唯一途徑，編譯器保證 TCO。
• C# 現狀：不支援 TCO，但理解尾遞歸與 CPS 能拓寬程式設計思維，對異步程式設計、狀態機實現、編譯器原理等領域極有裨益。

建議讀者嘗試用 CPS 實現更複雜的樹操作（如後序遍歷、路徑查找），體會「將控制流作為資料傳遞」的函數式精髓。