累加器传递模式(Accumulator passing style)
尾递归优化在于使堆栈可以不用保存上一次的返回地址/状态值，从而把递归函数当成一个普通的函数调用。
递归实际上是依赖上次的值，去求下次的值。 如果我们能把上次的值保存起来，在下次调用时传入，而不直接引用函数返回的值。 从而使堆栈释放，也就达到了尾递归优化的目的。
下面我们增加了一个acc的参数，它存储上次的值，在下次调用时传入。
|
1 2 3 4 5 6 |
static int Accumulate(int acc, int n) { if (n == 0) return acc; return accumulate(acc * n, n - 1); } |
使用时Accumulate递归时，我们仅需要使用最后一次的返回值即可。 调用如下：
|
1 |
var ac = Accumulate(1, 20); |
使用Lambda表达式实现尾递归阶乘：
|
1 2 3 4 5 6 |
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，中文一般译为后继传递模式。
|
1 2 3 4 5 |
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#写成下面函数来表示：
|
1 |
Console.WriteLine(Mult(a,Add(b,c))) |
操作步骤如下：
- b与c相加。
- 将结果乘以a。
- 输出结果。
执行1步时，后续操作是2,3。执行2步时，后续操作是3。 使用CPS模式来改造下times3函数：
|
1 2 3 4 5 |
static void Times3CPS(int x, Action<int> continuation) { continuation(x * 3); } Times3CPS(5, (reslut) => Console.WriteLine(result)); |
我们增加了一个表示后继操作3的函数参数，调用时传递后续操作，这就是CPS函数。
CPS变换
知道了CPS函数后，再详细看下CPS变换。
|
1 2 3 |
Console.WriteLine(Times3(5)); //CPS变换 Times3CPS(5, (reslut) => Console.WriteLine(result)); |
上面times3函数从直接调，到使用”后继传递操作”的过程就叫做CPS转换。
例如1：MAX函数的转换
