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