C#中的遞歸APS和CPS模式詳解
累加器傳遞模式(Accumulator passing style)
尾遞歸優(yōu)化在于使堆棧可以不用保存上一次的返回地址/狀態(tài)值，從而把遞歸函數(shù)當(dāng)成一個(gè)普通的函數(shù)調(diào)用。
遞歸實(shí)際上是依賴上次的值，去求下次的值。 如果我們能把上次的值保存起來(lái)，在下次調(diào)用時(shí)傳入，而不直接引用函數(shù)返回的值。 從而使堆棧釋放，也就達(dá)到了尾遞歸優(yōu)化的目的。
下面我們?cè)黾恿艘粋€(gè)acc的參數(shù)，它存儲(chǔ)上次的值，在下次調(diào)用時(shí)傳入。
static int Accumulate(int acc, int n)
{
if (n == 0)
return acc;
return accumulate(acc * n, n - 1);
}
使用時(shí)Accumulate遞歸時(shí)，我們僅需要使用最后一次的返回值即可。 調(diào)用如下：
var ac = Accumulate(1, 20);
使用Lambda表達(dá)式實(shí)現(xiàn)尾遞歸階乘：
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全稱Continuation passing style，中文一般譯為后繼傳遞模式。
static int Times3(int x)
{
return x * 3;
}
Console.WriteLine(Times3(5));
上面函數(shù)將輸入值乘以3，我們平?；旧隙紩?huì)這樣寫。 其實(shí)我們還可以用返回函數(shù)的C#語(yǔ)法，構(gòu)造嵌套方式，把函數(shù)的調(diào)用變成調(diào)用鏈times3(3)(5)。
這種方式在數(shù)學(xué)上或函數(shù)式編程中是比較直觀的，正常的，但在指令式語(yǔ)言c#中卻不是那么直觀。
CPS中的后繼(Continuation)一詞指的是計(jì)算的剩余部分，類似times3(3)(5)紅色這部分。
例如：表達(dá)式a*(b+c)的運(yùn)算過(guò)程有多個(gè)計(jì)算步驟。可以c#寫成下面函數(shù)來(lái)表示：
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ù)：
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變換。
Console.WriteLine(Times3(5));
//CPS變換
Times3CPS(5, (reslut) => Console.WriteLine(result));
上面times3函數(shù)從直接調(diào)，到使用"后繼傳遞操作"的過(guò)程就叫做CPS轉(zhuǎn)換。
例如1：MAX函數(shù)的轉(zhuǎn)換
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è)額外的類型參數(shù) Action，T是原始返回類型。
3：使用后續(xù)操作表達(dá)式參數(shù)替代原來(lái)所有返回聲明。
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。
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(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)的遞歸階乘：
static int Factorial(int n)
{
if (n == 0)
return 1;
else
return n * Factorial(n - 1);
}
使用同樣的步驟，把遞歸轉(zhuǎn)換成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));
}
“計(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)暴露給程序員，例如文中的例子。
相關(guān)文章
這篇文章主要介紹了C# XmlDocument操作XML案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了C#解析JSON的方法,主要采用了C#自帶的JavaScriptSerializer類來(lái)實(shí)現(xiàn),方法簡(jiǎn)單實(shí)用,需要的朋友可以參考下2014-09-09
C#將圖片存放到SQL SERVER數(shù)據(jù)庫(kù)中的方法
這篇文章主要介紹了C#將圖片存放到SQL SERVER數(shù)據(jù)庫(kù)中的方法,以實(shí)例形式較為詳細(xì)的分析了C#保存圖片到SQL Server數(shù)據(jù)庫(kù)的具體步驟與相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-09-09
winform實(shí)現(xiàn)拖動(dòng)文件到窗體上的方法
這篇文章主要介紹了winform實(shí)現(xiàn)拖動(dòng)文件到窗體上的方法,以實(shí)例分析了C#中WinForm操作窗體及文件的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-09-09
本文詳細(xì)講解了C#中的HttpWebRequest類的用法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-01-01
解決C#獲取鼠標(biāo)相對(duì)當(dāng)前窗口坐標(biāo)的實(shí)現(xiàn)方法
本篇文章是對(duì)在C#中獲取鼠標(biāo)相對(duì)當(dāng)前窗口坐標(biāo)的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C# 如何獲取處于運(yùn)行中的Excel、Word對(duì)象
這篇文章主要介紹了C# 獲取處于運(yùn)行中的Excel、Word對(duì)象操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-01-01
這篇文章主要介紹了C#中dotnetcharting的用法,以實(shí)例形式詳細(xì)分析了基于dotnetcharting的圖表繪制的各種常用方法,是非常實(shí)用的技巧,需要的朋友可以參考下2014-10-10
C#之HttpClient設(shè)置cookies的兩種方式
這篇文章主要介紹了C#之HttpClient設(shè)置cookies的兩種方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
這篇文章主要介紹了C# 生成隨機(jī)數(shù)的代碼的相關(guān)資料,非常的簡(jiǎn)單實(shí)用，需要的朋友可以參考下2015-03-03