一. 尾遞歸與Continuation
遞歸與尾遞歸
關于遞歸操作，相信大家都已經不陌生。簡單地說，一個函數直接或間接地調用自身，是為直接或間接遞歸。例如，我們可以使用遞歸來計算一個單向鏈表的長度：
public class Node
{
public Node(int value, Node next)
{
this.Value = value;
this.Next = next;
}
public int Value { get; private set; }
public Node Next { get; private set; }
}
編寫一個遞歸的GetLength方法：
public static int GetLengthRecursively(Node head)
{
if (head == null) return 0;
return GetLengthRecursively(head.Next) + 1;
}
在調用時，GetLengthRecursively方法會不斷調用自身，直至滿足遞歸出口。對遞歸有些了解的朋友一定猜得到，如果單項鏈表十分長，那么上面這個方法就可能會遇到棧溢出，也就是拋出StackOverflowException。這是由于每個線程在執行代碼時，都會分配一定尺寸的棧空間（Windows系統中為1M），每次方法調用時都會在棧里儲存一定信息（如參數、局部變量、返回地址等等），這些信息再少也會占用一定空間，成千上萬個此類空間累積起來，自然就超過線程的棧空間了。不過這個問題并非無解，我們只需把遞歸改成如下形式即可（在這篇文章里我們不考慮非遞歸的解法）：
public static int GetLengthTailRecursively(Node head, int acc)
{
if (head == null) return acc;
return GetLengthTailRecursively(head.Next, acc + 1);
}
GetLengthTailRecursively方法多了一個acc參數，acc的為accumulator（累加器）的縮寫，它的功能是在遞歸調用時“積累”之前調用的結果，并將其傳入下一次遞歸調用中——這就是GetLengthTailRecursively方法與GetLengthRecursively方法相比在遞歸方式上最大的區別：GetLengthRecursive方法在遞歸調用后還需要進行一次“+1”，而GetLengthTailRecursively的遞歸調用屬于方法的最后一個操作。這就是所謂的“尾遞歸”。與普通遞歸相比，由于尾遞歸的調用處于方法的最后，因此方法之前所積累下的各種狀態對于遞歸調用結果已經沒有任何意義，因此完全可以把本次方法中留在堆棧中的數據完全清除，把空間讓給最后的遞歸調用。這樣的優化1便使得遞歸不會在調用堆棧上產生堆積，意味著即時是“無限”遞歸也不會讓堆棧溢出。這便是尾遞歸的優勢。
有些朋友可能已經想到了，尾遞歸的本質，其實是將遞歸方法中的需要的“所有狀態”通過方法的參數傳入下一次調用中。對于GetLengthTailRecursively方法，我們在調用時需要給出acc參數的初始值：
GetLengthTailRecursively(head, 0)
為了進一步熟悉尾遞歸的使用方式，我們再用著名的“菲波納鍥”數列作為一個例子。傳統的遞歸方式如下：
public static int FibonacciRecursively(int n)
{
if (n < 2) return n;
return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
}
而改造成尾遞歸，我們則需要提供兩個累加器：
public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
if (n == 0) return acc1;
return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}
于是在調用時，需要提供兩個累加器的初始值：
FibonacciTailRecursively(10, 0, 1)
尾遞歸與Continuation
Continuation，即為“完成某件事情”之后“還需要做的事情”。例如，在.NET中標準的APM調用方式，便是由BeginXXX方法和EndXXX方法構成，這其實便是一種Continuation：在完成了BeginXXX方法之后，還需要調用EndXXX方法。而這種做法，也可以體現在尾遞歸構造中。例如以下為階乘方法的傳統遞歸定義：
public static int FactorialRecursively(int n)
{
if (n == 0) return 1;
return FactorialRecursively(n - 1) * n;
}
顯然，這不是一個尾遞歸的方式，當然我們輕易將其轉換為之前提到的尾遞歸調用方式。不過我們現在把它這樣“理解”：每次計算n的階乘時，其實是“先獲取n - 1的階乘”之后再“與n相乘并返回”，于是我們的FactorialRecursively方法可以改造成：
public static int FactorialRecursively(int n)
{
return FactorialContinuation(n - 1, r => n * r);
}
// 6. FactorialContinuation(n, x => x)
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
...
}
FactorialContinuation方法的含義是“計算n的階乘，并將結果傳入continuation方法，并返回其調用結果”。于是，很容易得出，FactorialContinuation方法自身便是一個遞歸調用：
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
return FactorialContinuation(n - 1,
r => continuation(n * r));
}
FactorialContinuation方法的實現可以這樣表述：“計算n的階乘，并將結果傳入continuation方法并返回”，也就是“計算n - 1的階乘，并將結果與n相乘，再調用continuation方法”。為了實現“并將結果與n相乘，再調用continuation方法”這個邏輯，代碼又構造了一個匿名方法，再次傳入FactorialContinuation方法。當然，我們還需要為它補充遞歸的出口條件：
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1,
r => continuation(n * r));
}
很明顯，FactorialContinuation實現了尾遞歸。如果要計算n的階乘，我們需要如下調用FactorialContinuation方法，表示“計算10的階乘，并將結果直接返回”：
FactorialContinuation(10, x => x)
再加深一下印象，大家是否能夠理解以下計算“菲波納鍥”數列第n項值的寫法？
public static int FibonacciContinuation(int n, Func<int, int> continuation)
{
if (n < 2) return continuation(n);
return FibonacciContinuation(n - 1,
r1 => FibonacciContinuation(n - 2,
r2 => continuation(r1 + r2)));
}
在函數式編程中，此類調用方式便形成了“Continuation Passing Style（CPS）”。由于C#的Lambda表達式能夠輕松構成一個匿名方法，我們也可以在C#中實現這樣的調用方式。您可能會想——汗，何必搞得這么復雜，計算階乘和“菲波納鍥”數列不是一下子就能轉換成尾遞歸形式的嗎？不過，您試試看以下的例子呢？
對二叉樹進行先序遍歷（pre-order traversal）是典型的遞歸操作，假設有如下TreeNode類：
public class TreeNode
{
public TreeNode(int value, TreeNode left, TreeNode right)
{
this.Value = value;
this.Left = left;
this.Right = right;
}
public int Value { get; private set; }
public TreeNode Left { get; private set; }
public TreeNode Right { get; private set; }
}
于是我們來傳統的先序遍歷一下：
public static void PreOrderTraversal(TreeNode root)
{
if (root == null) return;
Console.WriteLine(root.Value);
PreOrderTraversal(root.Left);
PreOrderTraversal(root.Right);
}
您能用“普通”的方式將它轉換為尾遞歸調用嗎？這里先后調用了兩次PreOrderTraversal，這意味著必然有一次調用沒法放在末尾。這時候便要利用到Continuation了：
public static void PreOrderTraversal(TreeNode root, Action<TreeNode> continuation)
{
if (root == null)
{
continuation(null);
return;
}
Console.WriteLine(root.Value);
PreOrderTraversal(root.Left,
left => PreOrderTraversal(root.Right,
right => continuation(right)));
}
我們現在把每次遞歸調用都作為代碼的最后一次操作，把接下來的操作使用Continuation包裝起來，這樣就實現了尾遞歸，避免了堆棧數據的堆積。可見，雖然使用Continuation是一個略有些“詭異”的使用方式，但是在某些時候它也是必不可少的使用技巧。
Continuation的改進
看看剛才的先序遍歷實現，您有沒有發現一個有些奇怪的地方？
PreOrderTraversal(root.Left,
left => PreOrderTraversal(root.Right,
right => continuation(right)));
關于最后一步，我們構造了一個匿名函數作為第二次PreOrderTraversal調用的Continuation，但是其內部直接調用了continuation參數——那么我們為什么不直接把它交給第二次調用呢？如下：
PreOrderTraversal(root.Left,
left => PreOrderTraversal(root.Right, continuation));
我們使用Continuation實現了尾遞歸，其實是把原本應該分配在棧上的信息丟到了托管堆上。每個匿名方法其實都是托管堆上的對象，雖然說這種生存周期短的對象不會對內存資源方面造成多大問題，但是盡可能減少此類對象，對于性能肯定是有幫助的。這里再舉一個更為明顯的例子，求二叉樹的大小（Size）：
public static int GetSize(TreeNode root, Func<int, int> continuation)
{
if (root == null) return continuation(0);
return GetSize(root.Left,
leftSize => GetSize(root.Right,
rightSize => continuation(leftSize + rightSize + 1)));
}
GetSize方法使用了Continuation，它的理解方法是“獲取root的大小，再將結果傳入continuation，并返回其調用結果”。我們可以將其進行改寫，減少Continuation方法的構造次數：
public static int GetSize2(TreeNode root, int acc, Func<int, int> continuation)
{
if (root == null) return continuation(acc);
return GetSize2(root.Left, acc,
accLeftSize => GetSize2(root.Right, accLeftSize + 1, continuation));
}
GetSize2方法多了一個累加器參數，同時它的理解方式也有了變化：“將root的大小累加到acc上，再將結果傳入continuation，并返回其調用結果”。也就是說GetSize2返回的其實是一個累加值，而并非是root參數的實際尺寸。當然，我們在調用時GetSize2時，只需將累加器置零便可：
GetSize2(root, 0, x => x)
不知您清楚了嗎？
結束
在命令式編程中，我們解決一些問題往往可以使用循環來代替遞歸，這樣便不會因為數據規模造成堆棧溢出。但是在函數式編程中，要實現“循環”的唯一方法便是“遞歸”，因此尾遞歸和CPS對于函數式編程的意義非常重大。了解尾遞歸，對于編程思維也有很大幫助，因此大家不妨多加思考和練習，讓這樣的方式為自己所用。
二. 淺談尾遞歸的優化方式
在上文《尾遞歸與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和contn調用FactorialContinuation時，都會構造一個新的contn - 1，并同n - 1傳入下一次FactorialContinuation調用中去。以此類推，直到n等于0時，就直接調用cont0并返回。至于每個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，還是無法簡單把遞歸優化成循環來避免堆棧溢出的。編譯器還必須進行其他方面的優化。
方法尾調用的優化
上一篇文章曾經談到：“與普通遞歸相比，由于尾遞歸的調用處于方法的最后，因此方法之前所積累下的各種狀態對于遞歸調用結果已經沒有任何意義，因此完全可以把本次方法中留在堆棧中的數據完全清除，把空間讓給最后的遞歸調用。這樣的優化便使得遞歸不會在調用堆棧上產生堆積，意味著即時是“無限”遞歸也不會讓堆棧溢出”。這其實才是尾遞歸的“正統”優化方式，那么我們先暫時忘記之前的“循環優化”，從最簡單的示例中查看這樣的優化是如何進行的。還是最簡單的“尾遞歸”階乘：
static int FactorialTailRecursion(int n, int acc)
{
if (n == 0) return acc;
return FactorialTailRecursion(n - 1, acc * n);
}
它的IL代碼是：
.method private hidebysig static int32 FactorialTailRecursion(int32 n, int32 acc) cil managed
{
.maxstack 8
L_0000: ldarg.0 // 加載第1個參數，即n
L_0001: brtrue.s L_0005 // 如果第一個參數不為0，則跳轉到L_0005
L_0003: ldarg.1 // 運行到此，說明第1個參數為0，則加載第2個參數，即acc
L_0004: ret // 返回（剛加載的第2個參數）
L_0005: ldarg.0 // 加載第1個參數，即n
L_0006: ldc.i4.1 // 加載數值1
L_0007: sub // 將兩者相減，即n - 1
L_0008: ldarg.1 // 加載第2個參數，即acc
L_0009: ldarg.0 // 加載第1個參數，即n
L_000a: mul // 將兩者相乘，即acc * n
// 把n - 1和acc * n作為參數遞歸調用
L_000b: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret // 返回遞歸調用結果
}
在這個問題上，我們還需要觀察它的匯編代碼（為了不干擾文章內容，我會把獲取匯編代碼的做法單獨寫一篇文章，稍后發布），如下：
00ad00d0 push ebp
00ad00d1 mov ebp,esp
00ad00d3 push esi
00ad00d4 mov eax,edx
00ad00d6 test ecx,ecx
00ad00d8 jne 00ad00dd
00ad00da pop esi
00ad00db pop ebp
00ad00dc ret
00ad00dd lea edx,[ecx-1]
00ad00e0 imul ecx,eax
00ad00e3 mov esi,ecx
00ad00e5 test edx,edx
00ad00e7 jne 00ad00ed
00ad00e9 mov eax,esi
00ad00eb jmp 00ad00f9
00ad00ed lea ecx,[edx-1]
00ad00f0 imul edx,esi
00ad00f3 call dword ptr ds:[703068h] (地址703068h的值即為00ad00d0)
00ad00f9 pop esi
00ad00fa pop ebp
00ad00fb ret
上面的匯編代碼非常簡單，從中可以看出，每次遞歸調用都使用了最簡單的call指令，沒有經過任何有效的優化或調整。因此在不斷地遞歸調用之后，終究會出現堆棧溢出。這就是普通遞歸的缺陷。而對于尾遞歸來說，MSIL提供了額外的tail指令表示“尾調用”1，它只需簡單補充在IL指令call, callvirt, calli之前便可。因此我們使用ildasm.exe將IL代碼dump出來，并在call之前加上tail指令：
.method private hidebysig static int32 FactorialTailRecursion(int32 n, int32 acc) cil managed
{
.maxstack 8
L_0000: ldarg.0
L_0001: brtrue.s L_0005
L_0003: ldarg.1
L_0004: ret
L_0005: ldarg.0
L_0006: ldc.i4.1
L_0007: sub
L_0008: ldarg.1
L_0009: ldarg.0
L_000a: mul
L_000b: tail.
L_000c: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret
}
使用ilasm.exe重新編譯之后運行，再重新察看FactorialTailRecursion的匯編代碼：
00a600d0 push ebp
00a600d1 mov ebp,esp
00a600d3 push edi
00a600d4 push esi
00a600d5 push ebx
00a600d6 mov eax,ecx
00a600d8 mov esi,edx
00a600da test eax,eax
00a600dc jne 00a600e5
00a600de mov eax,esi
00a600e0 pop ebx
00a600e1 pop esi
00a600e2 pop edi
00a600e3 pop ebp
00a600e4 ret
00a600e5 lea ecx,[eax-1]
00a600e8 imul eax,esi
00a600eb mov edx,eax
00a600ed mov eax,dword ptr ds:[813068h]
00a600f3 push 0
00a600f5 push 0
00a600f7 push 1
00a600f9 push eax
00a600fa cmp dword ptr [mscorwks!g_TrapReturningThreads (7204339c)],0
00a60101 je 00a6010c
00a60103 push ecx
00a60104 push edx
00a60105 call mscorwks!JIT_PollGC (71d5c9d3)
00a6010a pop edx
00a6010b pop ecx
00a6010c call mscorwks!JIT_TailCall (71b02890)
00a60111 int 3
在這里我實在無法完整講述上述匯編代碼的含義，不過從中可以看出它的確對于尾遞歸進行了特別的處理，而并非使用簡單的call指令進行調用。對此互聯網上的資源也不多，我只找到了Shri Borde的一篇文章，其中簡單描述了Whidbey V2（真早）中CLR對于這方面的處理，以及一些相關的考慮，從中似乎能夠看出一些苗頭來。
讓我們再回想之前的問題：Continuation無法通過簡單優化為循環來解決遞歸問題。但是通過觀察可以看出，Continuation.Invoke方法中的cont委托調用是最后一條命令，這說明它是一個“尾調用”——雖然不是“尾遞歸”，不過這已經滿足tail指令的要求了：只需和所在方法返回值相同（或兼容）即可。因此，對于Continuation來說，我們也需要進行尾遞歸的優化。您可以進行嘗試，現在無論遞歸多“深”，都不會使堆棧溢出了。
三. 尾遞歸對時間與空間復雜度的影響
以前我也在博客上簡單談過“尾遞歸”及其優化方式方面的話題。前幾天有同學在寫郵件向我提問，說是否所有的遞歸算法都能改寫為尾遞歸，改寫成尾遞歸之后，是否在時間和空間復雜度方面都能有所提高？他以斐波那契數列為例，似乎的確是這樣的情況。我當時的回答有些簡單，后來細想之后似乎感覺有點問題，而在仔細操作之后發現事情并沒有理論上那么簡單，
斐波那契數列
大家對于斐波那契數列（Fibonacci）的認識一定十分統一，唯一的區別可能僅在于n是從0開始還是從1開始算起。這里我們使用維基百科上的標準遞歸定義：
其邊界情況為：
使用這個定義可以直接寫出程序，這里我們用F#來表達：
let rec fib n =
if n < 2 then n
else fib (n - 1) + fib (n - 2)
這個算法最容易理解，但其時間復雜度確是：
這種指數級的時間復雜度在實際應用中是十分可怕的（雖然這個數字是美妙的黃金分割）。因此，我們如果真要“計算”斐波那契數列第n項的值（即不使用“通項公式”），則往往會使用迭代的方式進行，寫作尾遞歸則是：
let fibTail n =
// 第i項的值v1，以及即將累加上去的值v2
let rec fibTail' i v1 v2 =
if i >= n then v1
else fibTail' (i + 1) (v1 + v2) v1
fibTail' 0 0 1
從代碼上也可以輕易地判斷出，這個算法的時間復雜度是O(n)，實際上它也會被F#或是Scala等支持尾遞歸的編譯器優化為循環操作。這里我們使用命令式編程語言C#來表達編譯后的結果：
static int FibTail(int n, int i, int v1, int v2)
{
while (i < n)
{
int temp = v1 + v2;
v2 = v1;
v1 = temp;
i++;
}
return v1;
}
時間復雜度從O(1.618n)降低到O(n)，可謂是質的飛躍。
尾調用對空間復雜度的影響
那么，在空間復雜度方面，尾遞歸帶來什么優化嗎？我們首先還是來分析標準的遞歸算法：
假設，我們知道，在一個（無副作用的）方法執行完畢之后，除了返回值以外的空間會完全釋放出來，因此在fib(n - 2)執行結束之后，它的空間占用是常數級的。且fib(n - 1)的空間占用一定大于fib(n - 2)，假設其fib(n)的空間占用為S(n)，可得：
于是fib的空間復雜度是顯而易見的O(n)。這個空間復雜度其實并不大，例如經典的歸并排序算法的空間復雜度也同樣是O(n)。但不幸的是，這里的遞歸操作占用的完全是棧空間，而棧空間的大小是極其有限的（例如一個Windows應用程序默認情況下只有1M，ASP.NET甚至只有250K）。因此，只需一個稍大一點的數字會產生棧溢出。經試驗，在我的機器上只需51K便能出現StackOverflowException：
// 50K不會出現StackOverflowException
51 * 1024 |> fib |> printfn "%d"
那么尾遞歸算法的空間復雜度呢？我們剛才提到，編譯器會將尾遞歸優化成循環，那在實際運行時這個算法的空間復雜度自然是常數級，即O(1)。但這是我們實際觀察到的編譯器優化后的結果，從理論上說，我們并無法保證這里的尾遞歸會被優化成循環。因此我們不妨也從“字面”上來理解代碼，看看理論上這樣的尾遞歸調用會形成怎樣的空間占用。
對于尾遞歸來說，理論上我們只能期待它形成“尾調用”。也就是說，針對某個方法的調用（無論是否是遞歸操作）是父方法的最后一個操作。在這個情況下，我們無需保留父方法當前的棧空間，因此可以將其完全釋放。于是，無論調用多少次，只要每次都將棧空間釋放（或重用），其空間占用也始終是個常數，即O(1)。
因此，無論從理論上（從字面上分析）還是實際上（觀察編譯結果）來說，似乎將斐波那契數列修改為尾遞歸，能顯著地降低時間及空間復雜度，這也是那位同學提出“尾遞歸能改進時間和空間復雜度”的依據。那么我們重新回顧一下文章開頭所提出的兩個問題：
每個遞歸算法都能改寫為尾遞歸嗎？
改寫為尾遞歸都能改進時間及空間復雜度嗎？
