尾遞歸具體總結剖析。本站提示廣大學習愛好者：（尾遞歸具體總結剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是尾遞歸具體總結剖析正文
一. 尾遞歸與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)。
是以，不管從實際上（從字面上剖析）照樣現實上（不雅察編譯成果）來講，仿佛將斐波那契數列修正為尾遞歸，能明顯地下降時光及空間龐雜度，這也是那位同窗提出“尾遞歸能改良時光和空間龐雜度”的根據。那末我們從新回想一下文章開首所提出的兩個成績：
每一個遞歸算法都能改寫為尾遞歸嗎？
改寫為尾遞歸都能改良時光及空間龐雜度嗎？
