以前我也在博客上簡單談過“尾遞歸”及其優化方式方面的話題。前幾天有同學在寫郵件向我提問，說是否所有的遞歸算法都能改寫為尾遞歸，改寫成尾遞歸之后，是否在時間和空間復雜度方面都能有所提高？他以斐波那契數列為例，似乎的確是這樣的情況。我當時的回答有些簡單，后來細想之后似乎感覺有點問題，而在仔細操作之后發現事情并沒有理論上那么簡單，因此還是計劃寫篇文章來討論下這方面的問題。

斐波那契數列

大家對于斐波那契數列（Fibonacci）的認識一定十分統一，唯一的區別可能僅在于n是從0開始還是從1開始算起。這里我們使用維基百科上的標準遞歸定義：

其邊界情況為：

使用這個定義可以直接寫出程序，這里我們用F#來表達：

let rec fib n =if n < 2 then nelse fib (n - 1) + fib (n - 2)

這個算法最容易理解，但其時間復雜度確是：

這種指數級的時間復雜度在實際應用中是十分可怕的（雖然這個數字是美妙的黃金分割）。因此，我們如果真要“計算”斐波那契數列第n項的值（即不使用“通項公式”），則往往會使用迭代的方式進行，寫作尾遞歸則是：

let fibTail n = // 第i項的值v1，以及即將累加上去的值v2let rec fibTail' i v1 v2 =if i >= n then v1else fibTail' (i + 1) (v1 + v2) v1fibTail' 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.618ⁿ)降低到O(n)，可謂是質的飛躍。

尾調用對空間復雜度的影響

那么，在空間復雜度方面，尾遞歸帶來什么優化嗎？我們首先還是來分析標準的遞歸算法：

假設，我們知道，在一個（無副作用的）方法執行完畢之后，除了返回值以外的空間會完全釋放出來，因此在fib(n - 2)執行結束之后，它的空間占用是常數級的。且fib(n - 1)的空間占用一定大于fib(n - 2)，假設其fib(n)的空間占用為S(n)，可得：

于是fib的空間復雜度是顯而易見的O(n)。這個空間復雜度其實并不大，例如經典的歸并排序算法的空間復雜度也同樣是O(n)。但不幸的是，這里的遞歸操作占用的完全是棧空間，而?？臻g的大小是極其有限的（例如一個Windows應用程序默認情況下只有1M，ASP.NET甚至只有250K）。因此，只需一個稍大一點的數字會產生棧溢出。經試驗，在我的機器上只需51K便能出現StackOverflowException：

// 50K不會出現StackOverflowException 51 * 1024 |> fib |> printfn "%d"

那么尾遞歸算法的空間復雜度呢？我們剛才提到，編譯器會將尾遞歸優化成循環，那在實際運行時這個算法的空間復雜度自然是常數級，即O(1)。但這是我們實際觀察到的編譯器優化后的結果，從理論上說，我們并無法保證這里的尾遞歸會被優化成循環。因此我們不妨也從“字面”上來理解代碼，看看理論上這樣的尾遞歸調用會形成怎樣的空間占用。

對于尾遞歸來說，理論上我們只能期待它形成“尾調用”。也就是說，針對某個方法的調用（無論是否是遞歸操作）是父方法的最后一個操作。在這個情況下，我們無需保留父方法當前的?？臻g，因此可以將其完全釋放。于是，無論調用多少次，只要每次都將?？臻g釋放（或重用），其空間占用也始終是個常數，即O(1)。

因此，無論從理論上（從字面上分析）還是實際上（觀察編譯結果）來說，似乎將斐波那契數列修改為尾遞歸，能顯著地降低時間及空間復雜度，這也是那位同學提出“尾遞歸能改進時間和空間復雜度”的依據。那么我們重新回顧一下文章開頭所提出的兩個問題：

• 每個遞歸算法都能改寫為尾遞歸嗎？
• 改寫為尾遞歸都能改進時間及空間復雜度嗎？

下次我們繼續討論這兩個問題。

from:?http://blog.zhaojie.me/2011/11/does-tail-recursion-improve-time-and-space-complexities-1.html

總結

以上是生活随笔為你收集整理的尾递归对时间与空间复杂度的影响（上）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。