C#中的遞歸APS和CPS模式詳解
累加器傳遞模式(Accumulator passing style)
尾遞歸優(yōu)化在于使堆?？梢圆挥帽４嫔弦淮蔚姆祷氐刂?狀態(tài)值，從而把遞歸函數(shù)當成一個普通的函數(shù)調(diào)用。
遞歸實際上是依賴上次的值，去求下次的值。 如果我們能把上次的值保存起來，在下次調(diào)用時傳入，而不直接引用函數(shù)返回的值。 從而使堆棧釋放，也就達到了尾遞歸優(yōu)化的目的。
下面我們增加了一個acc的參數(shù)，它存儲上次的值，在下次調(diào)用時傳入。
static int Accumulate(int acc, int n)
{
if (n == 0)
return acc;
return accumulate(acc * n, n - 1);
}
使用時Accumulate遞歸時，我們僅需要使用最后一次的返回值即可。 調(diào)用如下：
var ac = Accumulate(1, 20);
使用Lambda表達式實現(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，我們平?；旧隙紩@樣寫。 其實我們還可以用返回函數(shù)的C#語法，構(gòu)造嵌套方式，把函數(shù)的調(diào)用變成調(diào)用鏈times3(3)(5)。
這種方式在數(shù)學上或函數(shù)式編程中是比較直觀的，正常的，但在指令式語言c#中卻不是那么直觀。
CPS中的后繼(Continuation)一詞指的是計算的剩余部分，類似times3(3)(5)紅色這部分。
例如：表達式a*(b+c)的運算過程有多個計算步驟?？梢詂#寫成下面函數(shù)來表示：
Console.WriteLine(Mult(a,Add(b,c)))
操作步驟如下：
1.b與c相加。
2.將結(jié)果乘以a。
3.輸出結(jié)果。
執(zhí)行1步時，后續(xù)操作是2,3。執(zhí)行2步時，后續(xù)操作是3。 使用CPS模式來改造下times3函數(shù)：
static void Times3CPS(int x, Action<int> continuation)
{
continuation(x * 3);
}
Times3CPS(5, (reslut) => Console.WriteLine(result));
我們增加了一個表示后繼操作3的函數(shù)參數(shù)，調(diào)用時傳遞后續(xù)操作，這就是CPS函數(shù)。
CPS變換
知道了CPS函數(shù)后，再詳細看下CPS變換。
Console.WriteLine(Times3(5));
//CPS變換
Times3CPS(5, (reslut) => Console.WriteLine(result));
上面times3函數(shù)從直接調(diào)，到使用"后繼傳遞操作"的過程就叫做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：添加一個額外的類型參數(shù) Action，T是原始返回類型。
3：使用后續(xù)操作表達式參數(shù)替代原來所有返回聲明。
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個函數(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風格，和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));
}
“計算n的階乘，并將結(jié)果傳入continuation方法并返回”，也就是“計算n - 1的階乘，并將結(jié)果與n相乘，再調(diào)用continuation方法”。為了實現(xiàn)“并將結(jié)果與n相乘，再調(diào)用continuation方法”這個邏輯，代碼又構(gòu)造了一個匿名方法，再次傳入Factorial方法。
總結(jié)
CPS模式是非常強大的，在很多方面都有使用，比如在編譯器實現(xiàn)中CPS風格的解析器組合子、函數(shù)完成后回調(diào)。也可以說是把程序內(nèi)部原本的控制操作，用CPS方法抽取出來暴露給程序員，例如文中的例子。
相關文章
這篇文章介紹了C#實現(xiàn)阿姆斯特朗數(shù)的算法，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-02-02
這篇文章主要介紹了利用FlubuCore用C#來寫DevOps腳本的方法，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-07-07
這篇文章主要為大家詳細介紹了C#如何使用讀寫鎖控制多線程寫入,文中的示例代碼講解詳細,具有一定的借鑒價值,感興趣的小伙伴可以跟隨小編一起學習一下2024-01-01
這篇文章主要介紹了C#使用ML.Net完成人工智能預測的詳細教程，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-12-12
這篇文章主要介紹了C#鍵盤輸入回車鍵實現(xiàn)點擊按鈕效果的方法,可實現(xiàn)用回車鍵代替點擊按鈕的功能,是非常實用的技巧,需要的朋友可以參考下2014-09-09
C#函數(shù)式編程中的遞歸調(diào)用之尾遞歸詳解
這篇文章主要介紹了C#函數(shù)式編程中的遞歸調(diào)用詳解,本文講解了什么是尾遞歸、尾遞歸的多種方式、尾遞歸的代碼實例等內(nèi)容,需要的朋友可以參考下2015-01-01
在C#中值類型的變量直接存儲數(shù)據(jù),而引用類型的變量持有的是數(shù)據(jù)的引用,數(shù)據(jù)存儲在數(shù)據(jù)堆中,下面這篇文章主要給大家介紹了關于C#基礎入門之值類型和引用類型區(qū)別的相關資料,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了c#如何使用 XML 文檔功能,幫助大家更好的理解和使用c#，感興趣的朋友可以了解下2020-10-10
這篇文章主要介紹了C#實現(xiàn)注冊碼的方法,可實現(xiàn)C#生成軟件注冊碼的相關功能,涉及C#硬件操作及隨機數(shù)操作的相關技巧,非常具有實用價值,需要的朋友可以參考下2015-08-08
WPF實現(xiàn)類似360安全衛(wèi)士界面的程序源碼分享
最近在網(wǎng)上看到了新版的360安全衛(wèi)士，感覺界面還不錯，于是用WPF制作了一個，時間有限，一些具體的控件沒有制作，用圖片代替了。感興趣的朋友一起跟著小編學習WPF實現(xiàn)類似360安全衛(wèi)士界面的程序源碼分享2015-09-09