在上文《尾遞歸與Continuation》里，我們談到了尾遞歸的概念和示例，不過有些朋友對于尾遞歸的功效依然有所懷疑。因此現在，老趙再簡單講解一下尾遞歸的優化原理，希望能給大家以一定理性認識。

尾遞歸的循環優化

　　尾遞歸，即是遞歸調用放在方法末尾的遞歸方式，如經典的階乘：

int FactorialTailRecursion(int n, int acc)
{
    if (n == 0) return acc;
    return FactorialTailRecursion(n - 1, acc * n);
}

　　由于遞歸在方法的末尾，因此方法中的局部變量已經毫無用處，編譯器完全可以將其“復用”，并把尾遞歸優化為“循環”方式：

int FactorialLoopOptimized(int n, int acc)
{
    while (true)
    {
        if (n == 0) return acc;

        acc *= n;
        n--;
    }
}

　　不過，上文還提到了尾遞歸中的常用技巧Continuation。那么對于如下形式的Continuation，編譯器又該如何優化呢？

int FactorialContinuation(int n, Func<int, int> continuation)
{
    if (n == 0) return continuation(1);
    return FactorialContinuation(n - 1, r => continuation(n * r));
}

　　我們先用“人腦”來思考一下，這段代碼的執行方式是怎么樣的。我們每次使用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.cont(this.n * r);
    }
}

public static int FactorialLoopOptimized3(int n, Func<int, int> continuation)
{
    while (true)
    {
        if (n == 0) break;
        continuation = new Continuation(continuation, n).Invoke;
        n--;
    }

    return continuation(1);
}

　　其實這才是FactorialContinuation的“直譯”，也是編譯器能夠進行優化。不過朋友們應該也能夠看出，這只是一個Continuation對象套著另一個Continuation對象。如果形成了數萬個Continuation對象的嵌套，在最終調用最外層的Continuation時，每個內部的Continuation也會在調用時往同一個堆棧中不斷累加，最終還是會造成堆棧溢出。因此，如果使用了Continuation，還是無法簡單把遞歸優化成循環來避免堆棧溢出的。編譯器還必須進行其他方面的優化。