首页 爱情文章 亲情文章 友情文章 生活随笔 校园文章 经典文章 人生哲理 励志文章 搞笑文章 心情日记
  • 爱情文章
  • 亲情文章
  • 友情文章
  • 生活随笔
  • 校园文章
  • 经典文章
  • 人生哲理
  • 励志文章
  • 搞笑文章
  • 心情日记
  • 英语文章
  • 范文大全
  • 作文大全
  • 新闻阅读
    •
    当前位置: 山茶花美文网 > 经典文章 > 正文

    [探索c#之递归APS和CPS]c/c++深层探索 pdf

    时间：2020-04-30来源：山茶花美文网 本文已影响 人 山茶花美文网手机站

    累加器传递模式(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 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 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 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 k)

    {

    G(n + 1, x = k(x + 1));

    }

    static void G(int n, Action 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 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方法抽取出来暴露给程序员，例如文中的例子。

    注：更多精彩教程请关注三联网页设计教程 栏目，

    • [探索c#之递归APS和CPS]c/c++深层探索 pdf 相关文章:
    • 爱情文章
    • 亲情文章
    • 友情文章
    • 随笔
    • 哲理
    • 励志
    • 范文大全

    最新文章

    热点文章

    推荐访问

    军训远足心得体会 军训爬山心得体会 大学军训徒步拉练感想 军训徒步作文 军训徒步10公里感想 军训徒步心得体会 5分钟演讲中秋节节日 中秋一分钟演讲 中秋节演讲稿4分钟 中秋节演讲稿一分钟 中秋节演讲稿五分钟 3-5分钟 中秋节短篇演讲稿 中秋节演讲稿两分钟 中秋节的演讲稿3分钟 关于中秋节的演讲稿三分钟 孩子体验军训的心得 参加孩子军训活动的感受与收获 家长对孩子军训后的收获和感悟 小孩军训的收获与感悟 学生军训的收获与感悟 孩子军训成长过程家长感悟 孩子军训感悟 孩子军训心得体会 孩子军训的收获与感悟 兵役前训练心得体会 部队当兵的心得 新兵役前教育训练心得体会 预备役军训心得体会 新兵军训感悟

    本文[探索c#之递归APS和CPS]c/c++深层探索 pdf由山茶花美文网整理提供，版权归原作者、原出处所有。

    Copyright © 山茶花美文网 All Rights Reserved.