這幾天恰好和朋友談起了遞歸，忽然發現不少朋友對於“尾遞歸”的概念比較模糊，網上搜索一番也 沒有發現講解地完整詳細的資料，於是寫了這麼一篇文章，權當一次互聯網資料的補充。
遞歸與尾遞歸
關於遞歸操作，相信大家都已經不陌生。簡單地說，一個函數直接或間接地調用自身，是為直接或間 接遞歸。例如，我們可以使用遞歸來計算一個單向鏈表的長度：
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對於函數式 編程的意義非常重大。了解尾遞歸，對於編程思維也有很大幫助，因此大家不妨多加思考和練習，讓這樣 的方式為自己所用。
注1：事實上，在C#中，即使您實現了尾遞歸，編譯器（包括C#編譯器及JIT）也不會進行優化，也就 是說還是無法避免StackOverflowException。我會在不久之後單獨討論一下這方面問題。
