探索c#之递归APS和CPS

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

累加器传递模式(APS)
CPS函数
CPS变换
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)))

操作步骤如下：

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