探索c#之递归APS和CPS

接上篇探索c#之尾递归编译器优化

  1. 累加器传递模式(APS)
  2. CPS函数
  3. CPS变换
  4. CPS尾递归
  5. 总结

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

操作步骤如下:

  • b与c相加。
  • 将结果乘以a。
  • 输出结果。

执行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方法抽取出来暴露给程序员,例如文中的例子。

参考资料

http://blogs.msdn.com/b/wesdyer/archive/2007/12/22/continuation-passing-style.aspx

探索C#之系列导航篇

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏非著名程序员

常见面试题六之java系列

做Android开发最重要的是要有一个很好的java基础。所以在我们的面试过程中也会被经常问到有关java的问题,其实在小编看来,如果java基础不好,那开发起...

1846
来自专栏Create Sun

基础拾遗------反射详解

前言 MSDN定义:通过 System.Reflection 命名空间中的类以及 System.Type,您可以获取有关已加载的程序集和在其中定义的类型(如类、...

3156
来自专栏blackheart的专栏

[C#1] 11-接口

接口与继承 CLR规定一个类型只能有一个基类型,这种继承成为单继承; 接口继承是指一个类型继承的是接口中的方法签名,而非方法实现,通常称为实现接口; 接口仅仅是...

2009
来自专栏风口上的猪的文章

.NET面试题系列[6] - 反射

在面试中,通常会考察反射的定义(操作元数据),可以用反射做什么(获得程序集及其各个部件),反射有什么使用场景(ORM,序列化,反序列化,值类型比较等)。如果答得...

992
来自专栏技术博客

设计模式之二(简单工厂模式)

  简单工厂模式根据提供的数据或者参数返回几个可能的类中的一个实例,说通俗点有点像面向对象编程中的多态性,一个基类,有多个派生类,在另外的调用程序中,根据参数来...

681
来自专栏GreenLeaves

C#核编之格式化编程

一、格式化控制台输入输出     1、 在前面的随笔中,会经常看到诸如{0},{1}之类的标记嵌入在字符串变量中。.NET引入一种字符串格式化的新风格。与C的p...

18510
来自专栏java架构师

C#字符串为空的几种情况

我们知道,在C#中,string是引用类型的。为空情况有以下三种: 1、  string str1="":会定义指针(栈),并在内存里划一块值为空的存储空间(堆...

2794
来自专栏博客园

.NET Core中延迟单例另一种写法【.NET Core和.NET Framework的beforefieldinit差异】

   前段时间在反编译代码时无意间看到在类中有一个BeforeFieldInit特性,处于好奇的心态查了查这个特性,发现这是一个关于字段初始化时间的特性【提前初...

1684
来自专栏技术博客

C#简单的面试题目(二)

实例化对象  new Class();        隐藏基类方法,即覆盖方法  public  new xxx(){}

1081
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(Function专栏)

汇总系列:https://www.cnblogs.com/dunitian/p/4822808.html#ai

1765

扫码关注云+社区