C#中的尾遞歸與Continuation詳解。本站提示廣大學習愛好者：（C#中的尾遞歸與Continuation詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C#中的尾遞歸與Continuation詳解正文
這幾天正好和同伙談起了遞歸，溘然發明很多同伙關於“尾遞歸”的概念比擬隱約，網上搜刮一番也沒有發明講授地完全具體的材料，因而寫了這麼一篇文章，權當一次互聯網材料的彌補。:P
遞歸與尾遞歸
關於遞歸操作，信任年夜家都曾經不生疏。簡略地說，一個函數直接或直接地挪用本身，是為直接或直接遞歸。例如，我們可使用遞歸來盤算一個單向鏈表的長度：
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。我會在不久以後零丁評論辯論一下這方面成績。
