萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> ASP.NET 程式設計

C# 遞迴進階:累加器模式 (APS) 與 續傳遞風格 (CPS) 深度解析

從一般遞迴到尾遞迴優化:APS 與 CPS 實戰

一般遞迴會累積呼叫堆疊,易造成 `StackOverflowException`。尾遞迴優化 (TCO) 可將遞迴轉為迴圈,C# 編譯器**不保證** TCO,需手動改寫為 APS 或 CPS 模式。

1. 累加器傳遞模式 (Accumulator Passing Style, APS)

將「上一層結果」作為參數傳遞給下一層,使遞迴呼叫成為**最後一個動作** (尾呼叫)。

階乘範例

// 一般遞迴 (非尾遞迴)
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

Lambda 表達式版本

static int FactorialAPS_Lambda(int x)
{
    Func accumulate = null;
    accumulate = (acc, n) => n == 0 ? acc : accumulate(acc * n, n - 1);
    return accumulate(1, x);
}

2. 續傳遞風格 (Continuation Passing Style, CPS)

不直接回傳值,而是接受一個「續傳函數」`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

CPS 變換步驟 (系統性)

  1. 回傳型別改為 `void`。
  2. 加入參數 `Action continuation` (T 為原回傳型別)。
  3. 所有 `return expr` 改為 `continuation(expr)`。
  4. 巢狀呼叫時,建立新 continuation 包裝後續邏輯。

Max 函數 CPS 轉換

// 原始
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

多層函數鏈 CPS 轉換 (F → G)

// 原始
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

3. CPS 尾遞迴:階乘

// 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」的邏輯被封裝在匿名函數中,傳遞給下一層遞迴。

4. 總結與應用場景

模式適用場景C# 實用性
APS簡單尾遞迴優化、數學累積運算高,易讀、效能佳
CPS非同步回呼、編譯器實作、協程、複雜控制流中,程式碼較難讀,但極具表達力

延伸閱讀: 老趙「尾遞迴與 Continuation」系列文章、F# `tailcall` 指令、C# 7.0+ `ref struct` 與 `Span` 在高效能遞迴中的應用。

copyright © 萬盛學電腦網 all rights reserved