程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> 探索c#之遞歸APS和CPS，

探索c#之遞歸APS和CPS，

編輯：C#入門知識

探索c#之遞歸APS和CPS，

接上篇探索c#之尾遞歸編譯器優化

累加器傳遞模式(Accumulator passing style)

尾遞歸優化在於使堆棧可以不用保存上一次的返回地址/狀態值，從而把遞歸函數當成一個普通的函數調用。
遞歸實際上是依賴上次的值，去求下次的值。如果我們能把上次的值保存起來，在下次調用時傳入，而不直接引用函數返回的值。從而使堆棧釋放，也就達到了尾遞歸優化的目的。

下面我們增加了一個acc的參數，它存儲上次的值，在下次調用時傳入。

static int Accumulate(int acc, int n)
    {
        if (n == 0)
            return acc;
        return accumulate(acc * n, n - 1);
    }

使用時Accumulate遞歸時，我們僅需要使用最後一次的返回值即可。調用如下：

 var ac = Accumulate(1, 20);

使用Lambda表達式實現尾遞歸階乘：

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

CPS函數

CPS全稱Continuation passing style，中文一般譯為後繼傳遞模式。

 static int Times3(int x)
    {
        return x * 3;
    }
   Console.WriteLine(Times3(5));

上面函數將輸入值乘以3，我們平常基本上都會這樣寫。其實我們還可以用返回函數的C#語法，構造嵌套方式，把函數的調用變成調用鏈times3(3)(5)。

這種方式在數學上或函數式編程中是比較直觀的，正常的，但在指令式語言c#中卻不是那麼直觀。

CPS中的後繼(Continuation)一詞指的是計算的剩余部分，類似times3(3)(5)紅色這部分。
例如：表達式a*(b+c)的運算過程有多個計算步驟。可以c#寫成下面函數來表示：

Console.WriteLine(Mult(a,Add(b,c)))

操作步驟如下：

b與c相加。
將結果乘以a。
輸出結果。

執行1步時，後續操作是2,3。執行2步時，後續操作是3。使用CPS模式來改造下times3函數：

static void Times3CPS(int x, Action<int> continuation)
    {
        continuation(x * 3);
    }
Times3CPS(5, (reslut) => Console.WriteLine(result));

我們增加了一個表示後繼操作3的函數參數，調用時傳遞後續操作，這就是CPS函數。

CPS變換

知道了CPS函數後，再詳細看下CPS變換。

Console.WriteLine(Times3(5)); 
//CPS變換
Times3CPS(5, (reslut) => Console.WriteLine(result));

上面times3函數從直接調，到使用"後繼傳遞操作"的過程就叫做CPS轉換。
例如1：MAX函數的轉換

static int Max(int n, int m)
{
    if (n > m)
        return n;
    else
        return m;
}
 Console.WriteLine(Max(3, 4));

我們把這max函數轉換成CPS模式，需要下列步驟：
1：返回值修改成void
2：添加一個額外的類型參數 Action，T是原始返回類型。
3：使用後續操作表達式參數替代原來所有返回聲明。

static void Max(int n, int m, Action<int> k)
{
    if (n > m)
        k(n);
    else
        k(m);
}
Max(3, 4, x => Console.WriteLine(x));

例如2：假如有3個函數Main、F、G，Main調用F、F調用G。

Console.WriteLine(F(1) + 1);
static int F(int n)
{
    return G(n + 1) + 1;
}
static int G(int n)
{
    return n + 1;
}

我們把F和G轉換成CPS風格，和Max函數同樣的轉換步驟：

F(1, x => Console.WriteLine(x + 1));
static void F(int n, Action<int> k)
{
    G(n + 1, x => k(x + 1));
}
static void G(int n, Action<int> k)
{
    k(n + 1);
}

CPS尾遞歸

這是傳統的遞歸階乘：

static int Factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * Factorial(n - 1);
}

使用同樣的步驟，把遞歸轉換成CPS尾遞歸:

Factorial(5, x => Console.WriteLine(x));
static void Factorial(int n, Action<int> continuation)
{
    if (n == 0)
        continuation(1);
    else
        Factorial(n - 1, x => continuation(n * x));
}

老趙-尾遞歸與Continuation

“計算n的階乘，並將結果傳入continuation方法並返回”，也就是“計算n - 1的階乘，並將結果與n相乘，再調用continuation方法”。為了實現“並將結果與n相乘，再調用continuation方法”這個邏輯，代碼又構造了一個匿名方法，再次傳入Factorial方法。