尾遞歸與Continuation的聯(lián)系
前面談了尾遞歸與Continuation，但是感覺還有些要補(bǔ)充下。
Continuation是一種非常古老的程序結(jié)構(gòu)，簡單說來就是entire default future of a computation, 即對程序“接下來要做的事情”所進(jìn)行的一種建模，即為“完成某件事情”之后“還需要做的事情”。而這種做法，也可以體現(xiàn)在尾遞歸構(gòu)造中。
例如以下為階乘方法的傳統(tǒng)遞歸定義：
1 | int FactorialRecursively(int n) |
4 | return FactorialRecursively(n - 1) * n; |
顯然，這不是一個(gè)尾遞歸的方式，當(dāng)然我們輕易將其轉(zhuǎn)換為之前提到的尾遞歸調(diào)用方式。不過我們現(xiàn)在把它這樣“理解”：每次計(jì)算n的階乘時(shí)，其實(shí)是“先獲取n - 1的階乘”之后再“與n相乘并返回”，于是我們的FactorialRecursively方法可以改造成：
01 | int FactorialRecursively(int n) |
03 | return FactorialContinuation(n - 1, r => n * r); |
06 | // FactorialContinuation(n, x => x) |
07 | int FactorialContinuation(int n, Func<int, int> continuation) |
FactorialContinuation方法的含義是“計(jì)算n的階乘，并將結(jié)果傳入continuation方法，并返回其調(diào)用結(jié)果”。于是，很容易得出，F(xiàn)actorialContinuation方法自身便是一個(gè)遞歸調(diào)用：
1 | public static int FactorialContinuation(int n, Func<int, int> continuation) |
3 | return FactorialContinuation(n - 1, |
4 | r => continuation(n * r)); |
FactorialContinuation方法的實(shí)現(xiàn)可以這樣表述：“計(jì)算n的階乘，并將結(jié)果傳入continuation方法并返回”，也就是“計(jì)算n - 1的階乘，并將結(jié)果與n相乘，再調(diào)用continuation方法”。為了實(shí)現(xiàn)“并將結(jié)果與n相乘，再調(diào)用continuation方法”這個(gè)邏輯，代碼又構(gòu)造了一個(gè)匿名方法，再次傳入FactorialContinuation方法。當(dāng)然，我們還需要為它補(bǔ)充遞歸的出口條件：
1 | public static int FactorialContinuation(int n, Func<int, int> continuation) |
3 | if (n == 0) return continuation(1); |
4 | return FactorialContinuation(n - 1, |
5 | r => continuation(n * r)); |
很明顯，F(xiàn)actorialContinuation實(shí)現(xiàn)了尾遞歸。如果要計(jì)算n的階乘，我們需要如下調(diào)用FactorialContinuation方法，表示“計(jì)算10的階乘，并將結(jié)果直接返回”：
1 | FactorialContinuation(10, x => x) |
再加深一下印象，大家是否能夠理解以下計(jì)算“斐波那契”數(shù)列第n項(xiàng)值的寫法？
1 | public static int FibonacciContinuation(int n, Func<int, int> continuation) |
3 | if (n < 2) return continuation(n); |
4 | return FibonacciContinuation(n - 1, |
5 | r1 => FibonacciContinuation(n - 2, |
6 | r2 => continuation(r1 + r2))); |
在函數(shù)式編程中，此類調(diào)用方式便形成了“Continuation Passing Style（CPS）”。由于C#的Lambda表達(dá)式能夠輕松構(gòu)成一個(gè)匿名方法，我們也可以在C#中實(shí)現(xiàn)這樣的調(diào)用方式。您可能會(huì)想——汗，何必搞得這么復(fù)雜，計(jì)算階乘和“斐波那契”數(shù)列不是一下子就能轉(zhuǎn)換成尾遞歸形式的嗎？不過，您試試看以下的例子呢？
對二叉樹進(jìn)行先序遍歷（pre-order traversal）是典型的遞歸操作，假設(shè)有如下TreeNode類：
03 | public TreeNode(int value, TreeNode left, TreeNode right) |
10 | public int Value { get; private set; } |
12 | public TreeNode Left { get; private set; } |
14 | public TreeNode Right { get; private set; } |
于是我們來傳統(tǒng)的先序遍歷一下：
1 | public static void PreOrderTraversal(TreeNode root) |
3 | if (root == null) return; |
5 | Console.WriteLine(root.Value); |
6 | PreOrderTraversal(root.Left); |
7 | PreOrderTraversal(root.Right); |
您能用“普通”的方式將它轉(zhuǎn)換為尾遞歸調(diào)用嗎？這里先后調(diào)用了兩次PreOrderTraversal，這意味著必然有一次調(diào)用沒法放在末尾。這時(shí)候便要利用到Continuation了：
01 | public static void PreOrderTraversal(TreeNode root, Action<TreeNode> continuation) |
09 | Console.WriteLine(root.Value); |
11 | PreOrderTraversal(root.Left, |
12 | left => PreOrderTraversal(root.Right, |
13 | right => continuation(right))); |
我們現(xiàn)在把每次遞歸調(diào)用都作為代碼的最后一次操作，把接下來的操作使用Continuation包裝起來，這樣就實(shí)現(xiàn)了尾遞歸，避免了堆棧數(shù)據(jù)的堆積。可見，雖然使用Continuation是一個(gè)略有些“詭異”的使用方式，但是在某些時(shí)候它也是必不可少的使用技巧。
Continuation的改進(jìn)
看看剛才的先序遍歷實(shí)現(xiàn)，您有沒有發(fā)現(xiàn)一個(gè)有些奇怪的地方？
1 | PreOrderTraversal(root.Left, |
2 | left => PreOrderTraversal(root.Right, |
3 | right => continuation(right))); |
關(guān)于最后一步，我們構(gòu)造了一個(gè)匿名函數(shù)作為第二次PreOrderTraversal調(diào)用的Continuation，但是其內(nèi)部直接調(diào)用了continuation參數(shù)——那么我們?yōu)槭裁床恢苯影阉唤o第二次調(diào)用呢？如下：
1 | PreOrderTraversal(root.Left, |
2 | left => PreOrderTraversal(root.Right, continuation)); |
我們使用Continuation實(shí)現(xiàn)了尾遞歸，其實(shí)是把原本應(yīng)該分配在棧上的信息丟到了托管堆上。每個(gè)匿名方法其實(shí)都是托管堆上的對象，雖然說這種生存周期短的對象不會(huì)對內(nèi)存資源方面造成多大問題，但是盡可能減少此類對象，對于性能肯定是有幫助的。這里再舉一個(gè)更為明顯的例子，求二叉樹的大?。⊿ize）：
1 | public static int GetSize(TreeNode root, Func<int, int> continuation) |
3 | if (root == null) return continuation(0); |
4 | return GetSize(root.Left, |
5 | leftSize => GetSize(root.Right, |
6 | rightSize => continuation(leftSize + rightSize + 1))); |
GetSize方法使用了Continuation，它的理解方法是“獲取root的大小，再將結(jié)果傳入continuation，并返回其調(diào)用結(jié)果”。我們可以將其進(jìn)行改寫，減少Continuation方法的構(gòu)造次數(shù)：
1 | public static int GetSize2(TreeNode root, int acc, Func<int, int> continuation) |
3 | if (root == null) return continuation(acc); |
4 | return GetSize2(root.Left, acc, |
5 | accLeftSize => GetSize2(root.Right, accLeftSize + 1, continuation)); |
GetSize2方法多了一個(gè)累加器參數(shù)，同時(shí)它的理解方式也有了變化：“將root的大小累加到acc上，再將結(jié)果傳入continuation，并返回其調(diào)用結(jié)果”。也就是說GetSize2返回的其實(shí)是一個(gè)累加值，而并非是root參數(shù)的實(shí)際尺寸。當(dāng)然，我們在調(diào)用時(shí)GetSize2時(shí)，只需將累加器置零便可：
1 | GetSize2(root, 0, x => x) |
小結(jié)
在命令式編程中，我們解決一些問題往往可以使用循環(huán)來代替遞歸，這樣便不會(huì)因?yàn)閿?shù)據(jù)規(guī)模造成堆棧溢出。但是在函數(shù)式編程中，要實(shí)現(xiàn)“循環(huán)”的唯一方法便是“遞歸”，因此尾遞歸和CPS對于函數(shù)式編程的意義非常重大。在函數(shù)式語言中，continuation的引入是非常自然的過程，實(shí)際上任何程序都可以通過所謂的CPS(Continuation Passing Style)變換而轉(zhuǎn)換為使用continuation結(jié)構(gòu)。了解尾遞歸，對于編程思維也有很大幫助，因此大家不妨多加思考和練習(xí)，讓這樣的方式為自己所用。
|
