探索c#之递归APS和CPS

[复制链接]
查看: 64|回复: 2
  • 慵懒
    2018-4-28 09:37
  • 发表于 2018-4-3 09:20:42 | 显示全部楼层 |阅读模式

    马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x

    累加器传递模式(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方法抽取出来暴露给程序员,例如文中的例子。


    发表于 2018-5-12 03:27:00 | 显示全部楼层
    啥也不说了,感谢楼主分享哇!
    回复

    使用道具 举报

    发表于 2018-6-3 07:04:14 | 显示全部楼层
    额,看不懂在说神马~@_@
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    精选推荐

     
     
    技术支持
    在线客服
    售后交流群瑞恩社区™售后</font><br><span>交流
    工作时间:
    8:00-18:00
    客服热线:
    15687827356
    微信扫一扫
    返回顶部 关注微信 下载APP 返回列表