一. 尾遞歸與Continuation
遞歸與尾遞歸
關(guān)于遞歸操作，相信大家都已經(jīng)不陌生。簡單地說，一個(gè)函數(shù)直接或間接地調(diào)用自身，是為直接或間接遞歸。例如，我們可以使用遞歸來計(jì)算一個(gè)單向鏈表的長度：
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; }
}
編寫一個(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)用自身，直至滿足遞歸出口。對遞歸有些了解的朋友一定猜得到，如果單項(xiàng)鏈表十分長，那么上面這個(gè)方法就可能會(huì)遇到棧溢出，也就是拋出StackOverflowException。這是由于每個(gè)線程在執(zhí)行代碼時(shí)，都會(huì)分配一定尺寸的棧空間（Windows系統(tǒng)中為1M），每次方法調(diào)用時(shí)都會(huì)在棧里儲存一定信息（如參數(shù)、局部變量、返回地址等等），這些信息再少也會(huì)占用一定空間，成千上萬個(gè)此類空間累積起來，自然就超過線程的棧空間了。不過這個(gè)問題并非無解，我們只需把遞歸改成如下形式即可（在這篇文章里我們不考慮非遞歸的解法）：
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（累加器）的縮寫，它的功能是在遞歸調(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)對于遞歸調(diào)用結(jié)果已經(jīng)沒有任何意義，因此完全可以把本次方法中留在堆棧中的數(shù)據(jù)完全清除，把空間讓給最后的遞歸調(diào)用。這樣的優(yōu)化1便使得遞歸不會(huì)在調(diào)用堆棧上產(chǎn)生堆積，意味著即時(shí)是“無限”遞歸也不會(huì)讓堆棧溢出。這便是尾遞歸的優(yōu)勢。
有些朋友可能已經(jīng)想到了，尾遞歸的本質(zhì)，其實(shí)是將遞歸方法中的需要的“所有狀態(tài)”通過方法的參數(shù)傳入下一次調(diào)用中。對于GetLengthTailRecursively方法，我們在調(diào)用時(shí)需要給出acc參數(shù)的初始值：
GetLengthTailRecursively(head, 0)
為了進(jìn)一步熟悉尾遞歸的使用方式，我們再用著名的“菲波納鍥”數(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)用方式。不過我們現(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)值的寫法？
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)換成尾遞歸形式的嗎？不過，您試試看以下的例子呢？
對二叉樹進(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; }
}
于是我們來傳統(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)用沒法放在末尾。這時(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)用都作為代碼的最后一次操作，把接下來的操作使用Continuation包裝起來，這樣就實(shí)現(xiàn)了尾遞歸，避免了堆棧數(shù)據(jù)的堆積。可見，雖然使用Continuation是一個(gè)略有些“詭異”的使用方式，但是在某些時(shí)候它也是必不可少的使用技巧。
Continuation的改進(jìn)
看看剛才的先序遍歷實(shí)現(xiàn)，您有沒有發(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í)都是托管堆上的對象，雖然說這種生存周期短的對象不會(huì)對內(nèi)存資源方面造成多大問題，但是盡可能減少此類對象，對于性能肯定是有幫助的。這里再舉一個(gè)更為明顯的例子，求二叉樹的大小（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)行改寫，減少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é)果”。也就是說GetSize2返回的其實(shí)是一個(gè)累加值，而并非是root參數(shù)的實(shí)際尺寸。當(dāng)然，我們在調(diào)用時(shí)GetSize2時(shí)，只需將累加器置零便可：
GetSize2(root, 0, x => x)
不知您清楚了嗎？
結(jié)束
在命令式編程中，我們解決一些問題往往可以使用循環(huán)來代替遞歸，這樣便不會(huì)因?yàn)閿?shù)據(jù)規(guī)模造成堆棧溢出。但是在函數(shù)式編程中，要實(shí)現(xiàn)“循環(huán)”的唯一方法便是“遞歸”，因此尾遞歸和CPS對于函數(shù)式編程的意義非常重大。了解尾遞歸，對于編程思維也有很大幫助，因此大家不妨多加思考和練習(xí)，讓這樣的方式為自己所用。
二. 淺談尾遞歸的優(yōu)化方式
在上文《尾遞歸與Continuation》里，我們談到了尾遞歸的概念和示例，不過有些朋友對于尾遞歸的功效依然有所懷疑。因此現(xiàn)在，我再簡單講解一下尾遞歸的優(yōu)化原理，希望能給大家以一定理性認(rèn)識。
尾遞歸的循環(huán)優(yōu)化
尾遞歸，即是遞歸調(diào)用放在方法末尾的遞歸方式，如經(jīng)典的階乘：
int FactorialTailRecursion(int n, int acc)
{
if (n == 0) return acc;
return FactorialTailRecursion(n - 1, acc * n);
}
由于遞歸在方法的末尾，因此方法中的局部變量已經(jīng)毫無用處，編譯器完全可以將其“復(fù)用”，并把尾遞歸優(yōu)化為“循環(huán)”方式：
int FactorialLoopOptimized(int n, int acc)
{
while (true)
{
if (n == 0) return acc;
acc *= n;
n--;
}
}
不過，上文還提到了尾遞歸中的常用技巧Continuation。那么對于如下形式的Continuation，編譯器又該如何優(yōu)化呢？
int FactorialContinuation(int n, Func<int, int> continuation)
{
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1, r => continuation(n * r));
}
我們先用“人腦”來思考一下，這段代碼的執(zhí)行方式是怎么樣的。我們每次使用n和contn調(diào)用FactorialContinuation時(shí)，都會(huì)構(gòu)造一個(gè)新的contn - 1，并同n - 1傳入下一次FactorialContinuation調(diào)用中去。以此類推，直到n等于0時(shí)，就直接調(diào)用cont0并返回。至于每個(gè)Continuation的定義，我們可以歸納出如下結(jié)果：
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!
于是，我們可以根據(jù)這個(gè)“意圖”，將FactorialContinuation方法“優(yōu)化”為如下形式：
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));
}
我們構(gòu)造了一個(gè)Continuation函數(shù)鏈表，隨著n遞減，每次都會(huì)把新的Continuation函數(shù)插入到鏈表頭，最后Aggregate方法會(huì)將第一個(gè)參數(shù)（累加器）依次運(yùn)用到每個(gè)函數(shù)中去，得到最后結(jié)果并返回。只可惜，這個(gè)優(yōu)化完全是我們“一廂情愿”而已，這么做的前提是“理解”了函數(shù)的意義，把方法的迭代調(diào)用“拆開”，而編譯器是無法（還是很難）幫我們優(yōu)化到如斯地步的。那么編譯器對于此類問題又該如何解決呢？
之前，我們使用C#中的匿名方法特性來構(gòu)造每個(gè)Continuation方法。如果我們使用自定義的封裝類，再將遞歸“優(yōu)化”成循環(huán)，F(xiàn)actorialContinuation又會(huì)成為什么樣呢？如下：
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);
}
其實(shí)這才是FactorialContinuation的“直譯”，也是編譯器能夠進(jìn)行優(yōu)化。不過朋友們應(yīng)該也能夠看出，這只是一個(gè)Continuation對象套著另一個(gè)Continuation對象。如果形成了數(shù)萬個(gè)Continuation對象的嵌套，在最終調(diào)用最外層的Continuation時(shí)，每個(gè)內(nèi)部的Continuation也會(huì)在調(diào)用時(shí)往同一個(gè)堆棧中不斷累加，最終還是會(huì)造成堆棧溢出。因此，如果使用了Continuation，還是無法簡單把遞歸優(yōu)化成循環(huán)來避免堆棧溢出的。編譯器還必須進(jìn)行其他方面的優(yōu)化。
方法尾調(diào)用的優(yōu)化
上一篇文章曾經(jīng)談到：“與普通遞歸相比，由于尾遞歸的調(diào)用處于方法的最后，因此方法之前所積累下的各種狀態(tài)對于遞歸調(diào)用結(jié)果已經(jīng)沒有任何意義，因此完全可以把本次方法中留在堆棧中的數(shù)據(jù)完全清除，把空間讓給最后的遞歸調(diào)用。這樣的優(yōu)化便使得遞歸不會(huì)在調(diào)用堆棧上產(chǎn)生堆積，意味著即時(shí)是“無限”遞歸也不會(huì)讓堆棧溢出”。這其實(shí)才是尾遞歸的“正統(tǒng)”優(yōu)化方式，那么我們先暫時(shí)忘記之前的“循環(huán)優(yōu)化”，從最簡單的示例中查看這樣的優(yōu)化是如何進(jìn)行的。還是最簡單的“尾遞歸”階乘：
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個(gè)參數(shù)，即n
L_0001: brtrue.s L_0005 // 如果第一個(gè)參數(shù)不為0，則跳轉(zhuǎn)到L_0005
L_0003: ldarg.1 // 運(yùn)行到此，說明第1個(gè)參數(shù)為0，則加載第2個(gè)參數(shù)，即acc
L_0004: ret // 返回（剛加載的第2個(gè)參數(shù)）
L_0005: ldarg.0 // 加載第1個(gè)參數(shù)，即n
L_0006: ldc.i4.1 // 加載數(shù)值1
L_0007: sub // 將兩者相減，即n - 1
L_0008: ldarg.1 // 加載第2個(gè)參數(shù)，即acc
L_0009: ldarg.0 // 加載第1個(gè)參數(shù)，即n
L_000a: mul // 將兩者相乘，即acc * n
// 把n - 1和acc * n作為參數(shù)遞歸調(diào)用
L_000b: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret // 返回遞歸調(diào)用結(jié)果
}
在這個(gè)問題上，我們還需要觀察它的匯編代碼（為了不干擾文章內(nèi)容，我會(huì)把獲取匯編代碼的做法單獨(dú)寫一篇文章，稍后發(fā)布），如下：
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
上面的匯編代碼非常簡單，從中可以看出，每次遞歸調(diào)用都使用了最簡單的call指令，沒有經(jīng)過任何有效的優(yōu)化或調(diào)整。因此在不斷地遞歸調(diào)用之后，終究會(huì)出現(xiàn)堆棧溢出。這就是普通遞歸的缺陷。而對于尾遞歸來說，MSIL提供了額外的tail指令表示“尾調(diào)用”1，它只需簡單補(bǔ)充在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重新編譯之后運(yùn)行，再重新察看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
在這里我實(shí)在無法完整講述上述匯編代碼的含義，不過從中可以看出它的確對于尾遞歸進(jìn)行了特別的處理，而并非使用簡單的call指令進(jìn)行調(diào)用。對此互聯(lián)網(wǎng)上的資源也不多，我只找到了Shri Borde的一篇文章，其中簡單描述了Whidbey V2（真早）中CLR對于這方面的處理，以及一些相關(guān)的考慮，從中似乎能夠看出一些苗頭來。
讓我們再回想之前的問題：Continuation無法通過簡單優(yōu)化為循環(huán)來解決遞歸問題。但是通過觀察可以看出，Continuation.Invoke方法中的cont委托調(diào)用是最后一條命令，這說明它是一個(gè)“尾調(diào)用”——雖然不是“尾遞歸”，不過這已經(jīng)滿足tail指令的要求了：只需和所在方法返回值相同（或兼容）即可。因此，對于Continuation來說，我們也需要進(jìn)行尾遞歸的優(yōu)化。您可以進(jìn)行嘗試，現(xiàn)在無論遞歸多“深”，都不會(huì)使堆棧溢出了。
三. 尾遞歸對時(shí)間與空間復(fù)雜度的影響
以前我也在博客上簡單談過“尾遞歸”及其優(yōu)化方式方面的話題。前幾天有同學(xué)在寫郵件向我提問，說是否所有的遞歸算法都能改寫為尾遞歸，改寫成尾遞歸之后，是否在時(shí)間和空間復(fù)雜度方面都能有所提高？他以斐波那契數(shù)列為例，似乎的確是這樣的情況。我當(dāng)時(shí)的回答有些簡單，后來細(xì)想之后似乎感覺有點(diǎn)問題，而在仔細(xì)操作之后發(fā)現(xiàn)事情并沒有理論上那么簡單，
斐波那契數(shù)列
大家對于斐波那契數(shù)列（Fibonacci）的認(rèn)識一定十分統(tǒng)一，唯一的區(qū)別可能僅在于n是從0開始還是從1開始算起。這里我們使用維基百科上的標(biāo)準(zhǔn)遞歸定義：
其邊界情況為：
使用這個(gè)定義可以直接寫出程序，這里我們用F#來表達(dá)：
let rec fib n =
if n < 2 then n
else fib (n - 1) + fib (n - 2)
這個(gè)算法最容易理解，但其時(shí)間復(fù)雜度確是：
這種指數(shù)級的時(shí)間復(fù)雜度在實(shí)際應(yīng)用中是十分可怕的（雖然這個(gè)數(shù)字是美妙的黃金分割）。因此，我們?nèi)绻嬉?ldquo;計(jì)算”斐波那契數(shù)列第n項(xiàng)的值（即不使用“通項(xiàng)公式”），則往往會(huì)使用迭代的方式進(jìn)行，寫作尾遞歸則是：
let fibTail n =
// 第i項(xiàng)的值v1，以及即將累加上去的值v2
let rec fibTail' i v1 v2 =
if i >= n then v1
else fibTail' (i + 1) (v1 + v2) v1
fibTail' 0 0 1
從代碼上也可以輕易地判斷出，這個(gè)算法的時(shí)間復(fù)雜度是O(n)，實(shí)際上它也會(huì)被F#或是Scala等支持尾遞歸的編譯器優(yōu)化為循環(huán)操作。這里我們使用命令式編程語言C#來表達(dá)編譯后的結(jié)果：
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;
}
時(shí)間復(fù)雜度從O(1.618n)降低到O(n)，可謂是質(zhì)的飛躍。
尾調(diào)用對空間復(fù)雜度的影響
那么，在空間復(fù)雜度方面，尾遞歸帶來什么優(yōu)化嗎？我們首先還是來分析標(biāo)準(zhǔn)的遞歸算法：
假設(shè)，我們知道，在一個(gè)（無副作用的）方法執(zhí)行完畢之后，除了返回值以外的空間會(huì)完全釋放出來，因此在fib(n - 2)執(zhí)行結(jié)束之后，它的空間占用是常數(shù)級的。且fib(n - 1)的空間占用一定大于fib(n - 2)，假設(shè)其fib(n)的空間占用為S(n)，可得：
于是fib的空間復(fù)雜度是顯而易見的O(n)。這個(gè)空間復(fù)雜度其實(shí)并不大，例如經(jīng)典的歸并排序算法的空間復(fù)雜度也同樣是O(n)。但不幸的是，這里的遞歸操作占用的完全是棧空間，而棧空間的大小是極其有限的（例如一個(gè)Windows應(yīng)用程序默認(rèn)情況下只有1M，ASP.NET甚至只有250K）。因此，只需一個(gè)稍大一點(diǎn)的數(shù)字會(huì)產(chǎn)生棧溢出。經(jīng)試驗(yàn)，在我的機(jī)器上只需51K便能出現(xiàn)StackOverflowException：
// 50K不會(huì)出現(xiàn)StackOverflowException
51 * 1024 |> fib |> printfn "%d"
那么尾遞歸算法的空間復(fù)雜度呢？我們剛才提到，編譯器會(huì)將尾遞歸優(yōu)化成循環(huán)，那在實(shí)際運(yùn)行時(shí)這個(gè)算法的空間復(fù)雜度自然是常數(shù)級，即O(1)。但這是我們實(shí)際觀察到的編譯器優(yōu)化后的結(jié)果，從理論上說，我們并無法保證這里的尾遞歸會(huì)被優(yōu)化成循環(huán)。因此我們不妨也從“字面”上來理解代碼，看看理論上這樣的尾遞歸調(diào)用會(huì)形成怎樣的空間占用。
對于尾遞歸來說，理論上我們只能期待它形成“尾調(diào)用”。也就是說，針對某個(gè)方法的調(diào)用（無論是否是遞歸操作）是父方法的最后一個(gè)操作。在這個(gè)情況下，我們無需保留父方法當(dāng)前的棧空間，因此可以將其完全釋放。于是，無論調(diào)用多少次，只要每次都將棧空間釋放（或重用），其空間占用也始終是個(gè)常數(shù)，即O(1)。
因此，無論從理論上（從字面上分析）還是實(shí)際上（觀察編譯結(jié)果）來說，似乎將斐波那契數(shù)列修改為尾遞歸，能顯著地降低時(shí)間及空間復(fù)雜度，這也是那位同學(xué)提出“尾遞歸能改進(jìn)時(shí)間和空間復(fù)雜度”的依據(jù)。那么我們重新回顧一下文章開頭所提出的兩個(gè)問題：
每個(gè)遞歸算法都能改寫為尾遞歸嗎？
改寫為尾遞歸都能改進(jìn)時(shí)間及空間復(fù)雜度嗎？
