您的位置：首页 > 编程技术 > csharp  >  C#中的递归APS和CPS模式详解

C#中的递归APS和CPS模式详解

 更新时间：2020年6月25日 11:31  点击：1885

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

[!--infotagslink--]

相关文章

  • C#实现简单的登录界面

    我们在使用C#做项目的时候，基本上都需要制作登录界面，那么今天我们就来一步步看看，如果简单的实现登录界面呢，本文给出2个例子，由简入难，希望大家能够喜欢。...2020-06-25

  • 浅谈C# 字段和属性

    这篇文章主要介绍了C# 字段和属性的的相关资料，文中示例代码非常详细，供大家参考和学习，感兴趣的朋友可以了解下...2020-11-03

  • C#中截取字符串的的基本方法详解

    这篇文章主要介绍了C#中截取字符串的的基本方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-11-03

  • C#实现简单的Http请求实例

    这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25

  • C#连接SQL数据库和查询数据功能的操作技巧

    本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧，本文通过图文并茂的形式给大家介绍的非常详细，需要的朋友参考下吧...2021-05-17

  • C#中new的几种用法详解

    本文主要介绍了C#中new的几种用法，具有很好的参考价值，下面跟着小编一起来看下吧...2020-06-25

  • 使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)

    这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2020-06-25

  • C#开发Windows窗体应用程序的简单操作步骤

    这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12

  • C#从数据库读取图片并保存的两种方法

    这篇文章主要介绍了C#从数据库读取图片并保存的方法，帮助大家更好的理解和使用c#，感兴趣的朋友可以了解下...2021-01-16

  • C#和JavaScript实现交互的方法

    最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现，故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25

  • C++调用C#的DLL程序实现方法

    本文通过例子，讲述了C++调用C#的DLL程序的方法，作出了以下总结，下面就让我们一起来学习吧。...2020-06-25

  • 轻松学习C#的基础入门

    轻松学习C#的基础入门，了解C#最基本的知识点，C#是一种简洁的，类型安全的一种完全面向对象的开发语言，是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言，需要的朋友可以参考下...2020-06-25

  • C#变量命名规则小结

    本文主要介绍了C#变量命名规则小结，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2021-09-09

  • C#绘制曲线图的方法

    这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25

  • C# 中如何取绝对值函数

    本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25

  • c#自带缓存使用方法 c#移除清理缓存

    这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法，需要的朋友可以参考下...2020-06-25

  • c#中(&&,||)与(&,|)的区别详解

    这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-06-25

  • 经典实例讲解C#递归算法

    这篇文章主要用实例讲解C#递归算法的概念以及用法，文中代码非常详细，帮助大家更好的参考和学习，感兴趣的朋友可以了解下...2020-06-25

  • C#学习笔记- 随机函数Random()的用法详解

    下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2020-06-25

  • C#中list用法实例

    这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25