C#中的尾遞歸與Continuation詳解
這幾天恰好和朋友談起了遞歸，忽然發(fā)現(xiàn)不少朋友對(duì)于“尾遞歸”的概念比較模糊，網(wǎng)上搜索一番也沒(méi)有發(fā)現(xiàn)講解地完整詳細(xì)的資料，于是寫(xiě)了這么一篇文章，權(quán)當(dāng)一次互聯(lián)網(wǎng)資料的補(bǔ)充。:P
遞歸與尾遞歸
關(guān)于遞歸操作，相信大家都已經(jīng)不陌生。簡(jiǎn)單地說(shuō)，一個(gè)函數(shù)直接或間接地調(diào)用自身，是為直接或間接遞歸。例如，我們可以使用遞歸來(lái)計(jì)算一個(gè)單向鏈表的長(zhǎng)度：
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; }
}
編寫(xiě)一個(gè)遞歸的GetLength方法：
public static int GetLengthRecursively(Node head)
{
if (head == null) return 0;
return GetLengthRecursively(head.Next) + 1;
}
在調(diào)用時(shí)，GetLengthRecursively方法會(huì)不斷調(diào)用自身，直至滿足遞歸出口。對(duì)遞歸有些了解的朋友一定猜得到，如果單項(xiàng)鏈表十分長(zhǎng)，那么上面這個(gè)方法就可能會(huì)遇到棧溢出，也就是拋出StackOverflowException。這是由于每個(gè)線程在執(zhí)行代碼時(shí)，都會(huì)分配一定尺寸的?？臻g（Windows系統(tǒng)中為1M），每次方法調(diào)用時(shí)都會(huì)在棧里儲(chǔ)存一定信息（如參數(shù)、局部變量、返回地址等等），這些信息再少也會(huì)占用一定空間，成千上萬(wàn)個(gè)此類空間累積起來(lái)，自然就超過(guò)線程的?？臻g了。不過(guò)這個(gè)問(wèn)題并非無(wú)解，我們只需把遞歸改成如下形式即可（在這篇文章里我們不考慮非遞歸的解法）：
public static int GetLengthTailRecursively(Node head, int acc)
{
if (head == null) return acc;
return GetLengthTailRecursively(head.Next, acc + 1);
}
GetLengthTailRecursively方法多了一個(gè)acc參數(shù)，acc的為accumulator（累加器）的縮寫(xiě)，它的功能是在遞歸調(diào)用時(shí)“積累”之前調(diào)用的結(jié)果，并將其傳入下一次遞歸調(diào)用中——這就是GetLengthTailRecursively方法與GetLengthRecursively方法相比在遞歸方式上最大的區(qū)別：GetLengthRecursive方法在遞歸調(diào)用后還需要進(jìn)行一次“+1”，而GetLengthTailRecursively的遞歸調(diào)用屬于方法的最后一個(gè)操作。這就是所謂的“尾遞歸”。與普通遞歸相比，由于尾遞歸的調(diào)用處于方法的最后，因此方法之前所積累下的各種狀態(tài)對(duì)于遞歸調(diào)用結(jié)果已經(jīng)沒(méi)有任何意義，因此完全可以把本次方法中留在堆棧中的數(shù)據(jù)完全清除，把空間讓給最后的遞歸調(diào)用。這樣的優(yōu)化1便使得遞歸不會(huì)在調(diào)用堆棧上產(chǎn)生堆積，意味著即時(shí)是“無(wú)限”遞歸也不會(huì)讓堆棧溢出。這便是尾遞歸的優(yōu)勢(shì)。
有些朋友可能已經(jīng)想到了，尾遞歸的本質(zhì)，其實(shí)是將遞歸方法中的需要的“所有狀態(tài)”通過(guò)方法的參數(shù)傳入下一次調(diào)用中。對(duì)于GetLengthTailRecursively方法，我們?cè)谡{(diào)用時(shí)需要給出acc參數(shù)的初始值：
GetLengthTailRecursively(head, 0)
為了進(jìn)一步熟悉尾遞歸的使用方式，我們?cè)儆弥摹胺撇{鍥”數(shù)列作為一個(gè)例子。傳統(tǒng)的遞歸方式如下：
public static int FibonacciRecursively(int n)
{
if (n < 2) return n;
return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
}
而改造成尾遞歸，我們則需要提供兩個(gè)累加器：
public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
if (n == 0) return acc1;
return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}
于是在調(diào)用時(shí)，需要提供兩個(gè)累加器的初始值：
FibonacciTailRecursively(10, 0, 1)
尾遞歸與Continuation
Continuation，即為“完成某件事情”之后“還需要做的事情”。例如，在.NET中標(biāo)準(zhǔn)的APM調(diào)用方式，便是由BeginXXX方法和EndXXX方法構(gòu)成，這其實(shí)便是一種Continuation：在完成了BeginXXX方法之后，還需要調(diào)用EndXXX方法。而這種做法，也可以體現(xiàn)在尾遞歸構(gòu)造中。例如以下為階乘方法的傳統(tǒng)遞歸定義：
public static int FactorialRecursively(int n)
{
if (n == 0) return 1;
return FactorialRecursively(n - 1) * n;
}
顯然，這不是一個(gè)尾遞歸的方式，當(dāng)然我們輕易將其轉(zhuǎn)換為之前提到的尾遞歸調(diào)用方式。不過(guò)我們現(xiàn)在把它這樣“理解”：每次計(jì)算n的階乘時(shí)，其實(shí)是“先獲取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方法的含義是“計(jì)算n的階乘，并將結(jié)果傳入continuation方法，并返回其調(diào)用結(jié)果”。于是，很容易得出，F(xiàn)actorialContinuation方法自身便是一個(gè)遞歸調(diào)用：
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
return FactorialContinuation(n - 1,
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ǔ)充遞歸的出口條件：
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1,
r => continuation(n * r));
}
很明顯，F(xiàn)actorialContinuation實(shí)現(xiàn)了尾遞歸。如果要計(jì)算n的階乘，我們需要如下調(diào)用FactorialContinuation方法，表示“計(jì)算10的階乘，并將結(jié)果直接返回”：
FactorialContinuation(10, x => x)
再加深一下印象，大家是否能夠理解以下計(jì)算“菲波納鍥”數(shù)列第n項(xiàng)值的寫(xiě)法？
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)));
}
在函數(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)換成尾遞歸形式的嗎？不過(guò)，您試試看以下的例子呢？
對(duì)二叉樹(shù)進(jìn)行先序遍歷（pre-order traversal）是典型的遞歸操作，假設(shè)有如下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; }
}
于是我們來(lái)傳統(tǒng)的先序遍歷一下：
public static void PreOrderTraversal(TreeNode root)
{
if (root == null) return;
Console.WriteLine(root.Value);
PreOrderTraversal(root.Left);
PreOrderTraversal(root.Right);
}
您能用“普通”的方式將它轉(zhuǎn)換為尾遞歸調(diào)用嗎？這里先后調(diào)用了兩次PreOrderTraversal，這意味著必然有一次調(diào)用沒(méi)法放在末尾。這時(shí)候便要利用到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)));
}
我們現(xiàn)在把每次遞歸調(diào)用都作為代碼的最后一次操作，把接下來(lái)的操作使用Continuation包裝起來(lái)，這樣就實(shí)現(xiàn)了尾遞歸，避免了堆棧數(shù)據(jù)的堆積?？梢?jiàn)，雖然使用Continuation是一個(gè)略有些“詭異”的使用方式，但是在某些時(shí)候它也是必不可少的使用技巧。
Continuation的改進(jìn)
看看剛才的先序遍歷實(shí)現(xiàn)，您有沒(méi)有發(fā)現(xiàn)一個(gè)有些奇怪的地方？
PreOrderTraversal(root.Left,
left => PreOrderTraversal(root.Right,
right => continuation(right)));
關(guān)于最后一步，我們構(gòu)造了一個(gè)匿名函數(shù)作為第二次PreOrderTraversal調(diào)用的Continuation，但是其內(nèi)部直接調(diào)用了continuation參數(shù)——那么我們?yōu)槭裁床恢苯影阉唤o第二次調(diào)用呢？如下：
PreOrderTraversal(root.Left,
left => PreOrderTraversal(root.Right, continuation));
我們使用Continuation實(shí)現(xiàn)了尾遞歸，其實(shí)是把原本應(yīng)該分配在棧上的信息丟到了托管堆上。每個(gè)匿名方法其實(shí)都是托管堆上的對(duì)象，雖然說(shuō)這種生存周期短的對(duì)象不會(huì)對(duì)內(nèi)存資源方面造成多大問(wèn)題，但是盡可能減少此類對(duì)象，對(duì)于性能肯定是有幫助的。這里再舉一個(gè)更為明顯的例子，求二叉樹(shù)的大小（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的大小，再將結(jié)果傳入continuation，并返回其調(diào)用結(jié)果”。我們可以將其進(jìn)行改寫(xiě)，減少Continuation方法的構(gòu)造次數(shù)：
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方法多了一個(gè)累加器參數(shù)，同時(shí)它的理解方式也有了變化：“將root的大小累加到acc上，再將結(jié)果傳入continuation，并返回其調(diào)用結(jié)果”。也就是說(shuō)GetSize2返回的其實(shí)是一個(gè)累加值，而并非是root參數(shù)的實(shí)際尺寸。當(dāng)然，我們?cè)谡{(diào)用時(shí)GetSize2時(shí)，只需將累加器置零便可：
GetSize2(root, 0, x => x)
不知您清楚了嗎？
結(jié)束
在命令式編程中，我們解決一些問(wèn)題往往可以使用循環(huán)來(lái)代替遞歸，這樣便不會(huì)因?yàn)閿?shù)據(jù)規(guī)模造成堆棧溢出。但是在函數(shù)式編程中，要實(shí)現(xiàn)“循環(huán)”的唯一方法便是“遞歸”，因此尾遞歸和CPS對(duì)于函數(shù)式編程的意義非常重大。了解尾遞歸，對(duì)于編程思維也有很大幫助，因此大家不妨多加思考和練習(xí)，讓這樣的方式為自己所用。
注1：事實(shí)上，在C#中，即使您實(shí)現(xiàn)了尾遞歸，編譯器（包括C#編譯器及JIT）也不會(huì)進(jìn)行優(yōu)化，也就是說(shuō)還是無(wú)法避免StackOverflowException。我會(huì)在不久之后單獨(dú)討論一下這方面問(wèn)題。
相關(guān)文章
這篇文章主要介紹了C# Dynamic關(guān)鍵字的相關(guān)資料，文中講解非常細(xì)致，對(duì)大家學(xué)習(xí)C# Dynamic關(guān)鍵字有所幫助，感興趣的朋友可以了解下2020-08-08
DirectoryInfo引用一個(gè)相對(duì)目錄的實(shí)例
這種特殊參數(shù)在Windows的命令提示符或者“運(yùn)行”對(duì)話框中都可以使用，等價(jià)于DOS中的cd命令參數(shù)。直接上代碼，一看你就懂了：2013-04-04
c#圖片縮放圖片剪切功能實(shí)現(xiàn)(等比縮放)
c#圖片縮放剪切功能實(shí)現(xiàn)，代碼中包含了c#圖片處理的一些基礎(chǔ)知識(shí),與大家分享2013-12-12
這篇文章主要為大家詳細(xì)介紹了Unity3D UGUI特效之Image高斯模糊效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-02-02
WPF開(kāi)發(fā)之UniformGrid和ItemsControl的應(yīng)用詳解
為了簡(jiǎn)化開(kāi)發(fā),WPF提供了UniformGrid布局和ItemsControl容器,本文以一個(gè)簡(jiǎn)單的小例子,簡(jiǎn)述如何在WPF開(kāi)發(fā)中應(yīng)用UniformGrid和ItemsControl實(shí)現(xiàn)均勻的布局,希望對(duì)大家有所幫助2024-01-01
本文主要介紹了C# 讀寫(xiě)XML的相關(guān)知識(shí)，具有很好的參考價(jià)值。下面跟著小編一起來(lái)看下吧2017-03-03
本文主要介紹了C# 枚舉Color并展示各種顏色效果，文中通過(guò)示例代碼介紹的非常詳細(xì)，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-07-07
這篇文章主要為大家詳細(xì)介紹了C# DataTable的使用方法，感興趣的小伙伴們可以參考一下2016-02-02
C#創(chuàng)建磁性窗體的實(shí)現(xiàn)方法
經(jīng)常會(huì)遇到一種情況,即當(dāng)拖動(dòng)一個(gè)窗體（主窗體）時(shí),其他窗體（子窗體）隨著該窗體移動(dòng),當(dāng)拖動(dòng)子窗體時(shí),其他窗體將不跟隨移動(dòng),這就是磁性窗體,所以本文給大家介紹了C#創(chuàng)建磁性窗體的實(shí)現(xiàn)方法,需要的朋友可以參考下2024-04-04
C#獲取時(shí)間戳的方法及時(shí)間戳轉(zhuǎn)換問(wèn)題
本文主要介紹了C#獲取時(shí)間戳的方法及時(shí)間戳轉(zhuǎn)換問(wèn)題，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02