浅谈尾递归的优化方式

我们先用“人脑”来思考一下，这段代码的执行方式是怎么样的。我们每次使用n和cont_n 调用FactorialContinuation时，都会构造一个新的cont_{n - 1}，并同n - 1传入下一次 FactorialContinuation调用中去。以此类推，直到n等于0时，就直接调用cont₀并返回。至 于每个Continuation的定义，我们可以归纳出如下结果：

Func<int,　int>　contn　=　r　=>　r　*　n

因此：

Factorial(n)
　　=　contn(contn　-　1(... (cont2(cont1(cont0(1)))...))
　　=　n　*　((n　–　1)　* 　(...(2　*　(1　*　1))...))　=　
　　=　n　*　(n　-　1)　*　...　*　2　*　1
　　=　 n!

于是，我们可以根据这个“意图”，将FactorialContinuation方法“优化”为如下形式：

int　FactorialLoopOptimized2(int　n,　Func<int,　int>　continuation)
{
　　LinkedList<Func<int,　int>>　contList　=　new　LinkedList<Func<int,　 int>>();

　　while　(true)
　　{
　　　　if　(n　==　0)　break;

　 　　　int　tempN　=　n;
　　　　Func<int,　int>　newCont　=　r　=>　tempN　*　 r;
　　　　contList.AddFirst(newCont);

　　　　n--;
　　　　continuation　=　 newCont;
　　}

　　return　contList.Aggregate(1,　(acc,　cont)　=>　cont (acc));
}

我们构造了一个Continuation函数链表，随着n递减，每次都会把新的Continuation函数插入到链表头 ，最后Aggregate方法会将第一个参数（累加器）依次运用到每个函数中去，得到最后结果并返回。只可 惜，这个优化完全是我们“一厢情愿”而已，这么做的前提是“理解”了函数的意义，把方法的迭代调用 “拆开”，而编译器是无法（还是很难）帮我们优化到如斯地步的。那么编译器对于此类问题又该如何解 决呢？

之前，我们使用C#中的匿名方法特性来构造每个Continuation方法。如果我们使用自定义的封装类， 再将递归“优化”成循环，FactorialContinuation又会成为什么样呢？如下：

private　class　Continuation
{
　　public　Continuation(Func<int,　int> 　cont,　int　n)
　　{
　　　　this.cont　=　cont;
　　　　this.n　=　n;
　　}

　　private　Func<int,　int>　cont;
　　private　int　n;

　　public 　int　Invoke(int　r)
　　{
　　　　return　this