一般遞迴會累積呼叫堆疊,易造成 `StackOverflowException`。尾遞迴優化 (TCO) 可將遞迴轉為迴圈,C# 編譯器**不保證** TCO,需手動改寫為 APS 或 CPS 模式。
將「上一層結果」作為參數傳遞給下一層,使遞迴呼叫成為**最後一個動作** (尾呼叫)。
// 一般遞迴 (非尾遞迴)
static int Factorial(int n)
=> n == 0 ? 1 : n * Factorial(n - 1);
// APS 尾遞迴
static int FactorialAPS(int acc, int n)
=> n == 0 ? acc : FactorialAPS(acc * n, n - 1);
// 呼叫
int result = FactorialAPS(1, 20); // acc 初始值為 1
static int FactorialAPS_Lambda(int x)
{
Func accumulate = null;
accumulate = (acc, n) => n == 0 ? acc : accumulate(acc * n, n - 1);
return accumulate(1, x);
}
不直接回傳值,而是接受一個「續傳函數」`continuation`,計算完成後呼叫它傳遞結果。將控制流顯式化,支援非同步、回呼、協程等進階模式。
// 一般函數
static int Times3(int x) => x * 3;
// CPS 版本
static void Times3CPS(int x, Action continuation)
=> continuation(x * 3);
// 呼叫
Times3CPS(5, result => Console.WriteLine(result)); // 輸出 15
// 原始
static int Max(int n, int m) => n > m ? n : m;
// CPS
static void MaxCPS(int n, int m, Action k)
{
if (n > m) k(n);
else k(m);
}
// 呼叫
MaxCPS(3, 4, x => Console.WriteLine(x)); // 輸出 4
// 原始
static int F(int n) => G(n + 1) + 1;
static int G(int n) => n + 1;
// CPS
static void F_CPS(int n, Action k)
=> G_CPS(n + 1, x => k(x + 1));
static void G_CPS(int n, Action k)
=> k(n + 1);
// 呼叫
F_CPS(1, x => Console.WriteLine(x)); // 輸出 3
// CPS 階乘
static void Factorial_CPS(int n, Action continuation)
{
if (n == 0)
continuation(1);
else
Factorial_CPS(n - 1, x => continuation(n * x));
}
// 呼叫
Factorial_CPS(5, x => Console.WriteLine(x)); // 輸出 120
關鍵洞察: `x => continuation(n * x)` 建立新 continuation,「乘以 n 然後呼叫原 continuation」的邏輯被封裝在匿名函數中,傳遞給下一層遞迴。
| 模式 | 適用場景 | C# 實用性 |
|---|---|---|
| APS | 簡單尾遞迴優化、數學累積運算 | 高,易讀、效能佳 |
| CPS | 非同步回呼、編譯器實作、協程、複雜控制流 | 中,程式碼較難讀,但極具表達力 |
延伸閱讀: 老趙「尾遞迴與 Continuation」系列文章、F# `tailcall` 指令、C# 7.0+ `ref struct` 與 `Span` 在高效能遞迴中的應用。