C#中的递归APS和CPS模式详解
累加器传递模式(Accumulatorpassingstyle)
尾递归优化在于使堆栈可以不用保存上一次的返回地址/状态值，从而把递归函数当成一个普通的函数调用。
递归实际上是依赖上次的值，去求下次的值。如果我们能把上次的值保存起来，在下次调用时传入，而不直接引用函数返回的值。从而使堆栈释放，也就达到了尾递归优化的目的。
下面我们增加了一个acc的参数，它存储上次的值，在下次调用时传入。
staticintAccumulate(intacc,intn)
{
if(n==0)
returnacc;
returnaccumulate(acc*n,n-1);
}
使用时Accumulate递归时，我们仅需要使用最后一次的返回值即可。调用如下：
varac=Accumulate(1,20);
使用Lambda表达式实现尾递归阶乘：
staticintAccumulateByLambda(intx)
{
Func<int,int,int>accumulate=null;
accumulate=(acc,n)=>n==0?acc:Accumulate(acc*n,n-1);
returnaccumulate(1,x);
}
CPS函数
CPS全称Continuationpassingstyle，中文一般译为后继传递模式。
staticintTimes3(intx)
{
returnx*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函数：
staticvoidTimes3CPS(intx,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函数的转换
staticintMax(intn,intm)
{
if(n>m)
returnn;
else
returnm;
}
Console.WriteLine(Max(3,4));
我们把这max函数转换成CPS模式，需要下列步骤：
1：返回值修改成void
2：添加一个额外的类型参数Action，T是原始返回类型。
3：使用后续操作表达式参数替代原来所有返回声明。
staticvoidMax(intn,intm,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);
staticintF(intn)
{
returnG(n+1)+1;
}
staticintG(intn)
{
returnn+1;
}
我们把F和G转换成CPS风格，和Max函数同样的转换步骤：
F(1,x=>Console.WriteLine(x+1));
staticvoidF(intn,Action<int>k)
{
G(n+1,x=>k(x+1));
}
staticvoidG(intn,Action<int>k)
{
k(n+1);
}
CPS尾递归
这是传统的递归阶乘：
staticintFactorial(intn)
{
if(n==0)
return1;
else
returnn*Factorial(n-1);
}
使用同样的步骤，把递归转换成CPS尾递归:
Factorial(5,x=>Console.WriteLine(x));
staticvoidFactorial(intn,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方法抽取出来暴露给程序员，例如文中的例子。