程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> C#中的遞歸APS和CPS形式詳解

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

編輯:C#入門知識

C#中的遞歸APS和CPS形式詳解。本站提示廣大學習愛好者:(C#中的遞歸APS和CPS形式詳解)文章只能為提供參考,不一定能成為您想要的結果。以下是C#中的遞歸APS和CPS形式詳解正文


累加器傳遞形式(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)))

操作步調以下:

1.b與c相加。
2.將成果乘以a。
3.輸入成果。

履行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辦法。

總結

CPS形式長短常壯大的,在許多方面都有應用,好比在編譯器完成中CPS作風的解析器組合子、函數完成後回調。也能夠說是把法式外部本來的掌握操作,用CPS辦法抽掏出來裸露給法式員,例如文中的例子。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved