腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

C#中的遞歸APS和CPS模式詳解

更新時(shí)間：2015年04月10日 09:21:52 投稿：junjie

這篇文章主要介紹了C#中的遞歸APS和CPS模式詳解,本文講解了累加器傳遞模式、CPS函數(shù)、CPS變換、CPS尾遞歸、尾遞歸與Continuation等內(nèi)容,需要的朋友可以參考下

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

尾遞歸優(yōu)化在于使堆?？梢圆挥帽４嫔弦淮蔚姆祷氐刂?狀態(tài)值，從而把遞歸函數(shù)當(dāng)成一個(gè)普通的函數(shù)調(diào)用。

遞歸實(shí)際上是依賴(lài)上次的值，去求下次的值。如果我們能把上次的值保存起來(lái)，在下次調(diào)用時(shí)傳入，而不直接引用函數(shù)返回的值。從而使堆棧釋放，也就達(dá)到了尾遞歸優(yōu)化的目的。

下面我們?cè)黾恿艘粋€(gè)acc的參數(shù)，它存儲(chǔ)上次的值，在下次調(diào)用時(shí)傳入。

復(fù)制代碼代碼如下:

static int Accumulate(int acc, int n)

    {

        if (n == 0)

            return acc;

        return accumulate(acc * n, n - 1);

    }

使用時(shí)Accumulate遞歸時(shí)，我們僅需要使用最后一次的返回值即可。調(diào)用如下：

復(fù)制代碼代碼如下:

var ac = Accumulate(1, 20);

使用Lambda表達(dá)式實(shí)現(xiàn)尾遞歸階乘：

復(fù)制代碼代碼如下:

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函數(shù)

CPS全稱(chēng)Continuation passing style，中文一般譯為后繼傳遞模式。

復(fù)制代碼代碼如下:

 static int Times3(int x)

    {

        return x * 3;

    }

   Console.WriteLine(Times3(5));

上面函數(shù)將輸入值乘以3，我們平?；旧隙紩?huì)這樣寫(xiě)。其實(shí)我們還可以用返回函數(shù)的C#語(yǔ)法，構(gòu)造嵌套方式，把函數(shù)的調(diào)用變成調(diào)用鏈times3(3)(5)。

這種方式在數(shù)學(xué)上或函數(shù)式編程中是比較直觀的，正常的，但在指令式語(yǔ)言c#中卻不是那么直觀。

CPS中的后繼(Continuation)一詞指的是計(jì)算的剩余部分，類(lèi)似times3(3)(5)紅色這部分。
例如：表達(dá)式a*(b+c)的運(yùn)算過(guò)程有多個(gè)計(jì)算步驟?？梢詂#寫(xiě)成下面函數(shù)來(lái)表示：

復(fù)制代碼代碼如下:

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

操作步驟如下：

1.b與c相加。
2.將結(jié)果乘以a。
3.輸出結(jié)果。

執(zhí)行1步時(shí)，后續(xù)操作是2,3。執(zhí)行2步時(shí)，后續(xù)操作是3。使用CPS模式來(lái)改造下times3函數(shù)：

復(fù)制代碼代碼如下:

static void Times3CPS(int x, Action<int> continuation)

    {

        continuation(x * 3);

    }

Times3CPS(5, (reslut) => Console.WriteLine(result));

我們?cè)黾恿艘粋€(gè)表示后繼操作3的函數(shù)參數(shù)，調(diào)用時(shí)傳遞后續(xù)操作，這就是CPS函數(shù)。

CPS變換

知道了CPS函數(shù)后，再詳細(xì)看下CPS變換。

復(fù)制代碼代碼如下:

Console.WriteLine(Times3(5)); 

//CPS變換

Times3CPS(5, (reslut) => Console.WriteLine(result));

上面times3函數(shù)從直接調(diào)，到使用"后繼傳遞操作"的過(guò)程就叫做CPS轉(zhuǎn)換。
例如1：MAX函數(shù)的轉(zhuǎn)換

復(fù)制代碼代碼如下:

static int Max(int n, int m)

{

    if (n > m)

        return n;

    else

        return m;

}

 Console.WriteLine(Max(3, 4));

我們把這max函數(shù)轉(zhuǎn)換成CPS模式，需要下列步驟：
1：返回值修改成void
2：添加一個(gè)額外的類(lèi)型參數(shù) Action，T是原始返回類(lèi)型。
3：使用后續(xù)操作表達(dá)式參數(shù)替代原來(lái)所有返回聲明。

復(fù)制代碼代碼如下:

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個(gè)函數(shù)Main、F、G，Main調(diào)用F、F調(diào)用G。

復(fù)制代碼代碼如下:

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轉(zhuǎn)換成CPS風(fēng)格，和Max函數(shù)同樣的轉(zhuǎn)換步驟：

復(fù)制代碼代碼如下:

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尾遞歸

這是傳統(tǒng)的遞歸階乘：

復(fù)制代碼代碼如下:

static int Factorial(int n)

{

    if (n == 0)

        return 1;

    else

        return n * Factorial(n - 1);

}

使用同樣的步驟，把遞歸轉(zhuǎn)換成CPS尾遞歸:

復(fù)制代碼代碼如下:

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

“計(jì)算n的階乘，并將結(jié)果傳入continuation方法并返回”，也就是“計(jì)算n - 1的階乘，并將結(jié)果與n相乘，再調(diào)用continuation方法”。為了實(shí)現(xiàn)“并將結(jié)果與n相乘，再調(diào)用continuation方法”這個(gè)邏輯，代碼又構(gòu)造了一個(gè)匿名方法，再次傳入Factorial方法。

總結(jié)

CPS模式是非常強(qiáng)大的，在很多方面都有使用，比如在編譯器實(shí)現(xiàn)中CPS風(fēng)格的解析器組合子、函數(shù)完成后回調(diào)。也可以說(shuō)是把程序內(nèi)部原本的控制操作，用CPS方法抽取出來(lái)暴露給程序員，例如文中的例子。

您可能感興趣的文章: