1.2.2 樹形遞歸

另一種常見計算模式稱為樹形遞歸。作為例子，現在考慮斐波那契（Fibonacci）數序列的計算，這一序列中的每個數都是前面兩個數之和：

0, 1, 1, 2, 3, 5, 8, 13, 21,…

一般而言，斐波那契數由下面的規則定義：

我們立刻就能把這個定義翻譯為一個計算斐波那契數的遞歸函數：

現在考慮這一計算的模式。為了計算fib（5），我們需要計算fib（4）和fib（3）。而為了計算fib（4），又需要計算fib（3）和fib（2）。一般而言，這一演化過程看起來像一棵樹，如圖1.5所示。請注意，這里的分支在每一層分裂為兩個分支（除了最下面的），反映出對fib函數的每個調用里兩次遞歸調用自身的事實。

上面這個函數作為典型的樹形遞歸很有教育意義，但對計算斐波那契數而言，它卻是一種很糟糕的方法，因為做了太多的冗余計算。從圖1.5中可以看到，對fib（3）的全部計算重復做了兩次，差不多占到所有工作的一半。事實上，不難證明，在整個計算過程中，計算fib（1）和fib（0）的次數（一般來說，也就是上面這種樹里的樹葉數）正好是Fib（n+1）。要感受一下這種情況有多糟，我們可以證明Fib（n）值的增長相對于n是指數的。更準確地說（見練習1.13），Fib（n）等于最接近的那個整數，其中：

這也就是黃金分割的值，它滿足方程：

?2=?+1

這樣，這個計算過程中所用的步驟數將隨著輸入的增長而指數增長。在另一方面，其空間需求只是隨著輸入的增長而線性增長，因為，在計算中的每一點，我們都只需要保存樹中在此結點之上的結點的軌跡。一般而言，樹形遞歸計算過程里所需要的步驟數正比于樹中的結點數，其空間需求正比于樹的最大深度。

我們也可以規劃出一種計算斐波那契數的迭代計算過程，其基本想法就是用一對整數a和b，把它們分別初始化為Fib（1）=1和Fib（0）=0，然后反復地同時應用下面的變換規則：

a←a+b

b←a

不難證明，在n次應用這些變換后，a和b將分別等于Fib（n+1）和Fib（n）。因此，我們可以定義下面這兩個函數，以迭代方式計算斐波那契數：

這種計算Fib（n）的方法是線性迭代。這兩種方法在所需步數上差異巨大——后一個相對n為線性的，前一個增長得如Fib（n）一樣快——即使不大的輸入也可能造成巨大差異。

然而，我們也不應該做出結論說樹形遞歸計算過程根本沒用。如果需要考慮操作具有層次結構的數據（而不是操作數值），我們可能發現樹形遞歸計算過程是一種很自然的、威力強大的工具[30]。即使對于數的計算，樹形遞歸計算過程也可能幫助我們理解和設計程序。以計算斐波那契數的程序為例，雖然第一個fib函數遠比第二個低效，但它卻更直截了當，幾乎就是把斐波那契序列的定義直接翻譯為JavaScript。而要規劃出對應的迭代算法，就需要注意到該計算過程可以重塑為一個采用三個狀態變量的迭代。

實例：換零錢方式的統計

要找到迭代的斐波那契算法，只需要不多的智慧。下面這個問題的情況與此不同：我們有一些50美分、25美分、10美分、5美分和1美分的硬幣，要把1美元換成零錢，一共有多少種不同的方式？更一般的問題是，給了任意數量的美元現金，我們能寫出一個程序，計算出所有換零錢方式的數目嗎？

如果采用遞歸函數，這個問題有一種很簡單的解法。假定我們把考慮的可用硬幣類按某種順序排好，于是就有下面的關系。

把總數為a的現金換成n種硬幣的不同方式的數目等于

現金a換成除去第一種硬幣之外的所有其他硬幣的不同方式數目

加上現金a-d換成所有種類的硬幣的不同方式數目，其中d是第一種硬幣的幣值

要弄清為什么這一說法正確，請注意這里把換零錢的方式分成兩組，第一組的換法都沒用第一種硬幣，而第二組都用了第一種硬幣。顯然，換零錢的全部換法的數目，就等于完全不用第一種硬幣的換法數，加上用了第一種硬幣的換零錢的換法數。而后一個數目也就等于去掉一個第一種硬幣值后，將剩下的現金換零錢的換法數。

這樣，我們就把某個給定現金數的換零錢方式的問題，遞歸地歸約為對更少現金數或者更少硬幣種類的同一個問題。請仔細考慮上面的歸約規則，設法使自己確信，如果采用下面的方法處理各種退化情況，我們就能利用上述規則寫出一個算法[31]：

●如果a就是0，應該算作有1種換零錢的方式。

●如果a小于0，應該算作有0種換零錢的方式。

●如果n是0，應該算作有0種換零錢的方式。

我們很容易把這些規則翻譯成一個遞歸函數：

（函數first_denomination以可用硬幣的種類數作為輸入，返回第一種硬幣的幣值。這里認為硬幣已經從最小到最大排好了，其實采用任何順序都可以。）我們現在就能回答開始的問題了，下面是1美元換硬幣的不同方法的數目：

函數count_change產生樹形遞歸的計算過程，其中的冗余計算與前面fib的第一種實現類似。但另一方面，想設計一個能算出同樣結果的更好的算法，就不那么明顯了。我們把這個問題留給讀者作為一個挑戰。可以看到，樹形遞歸的計算過程可能極其低效，但常常很容易描述和理解，這導致有人提出能否利用這兩個世界里最好的東西設計一種“聰明編譯器”，使之能把樹形遞歸的函數翻譯為能完成同樣計算的更高效的函數[32]。

練習1.11 函數f由如下規則定義：如果n<3，那么f（n）=n；如果n≥3，那么f（n）=f（n-1）+2f（n-2）+3f（n-3）。請寫一個JavaScript函數，它通過一個遞歸計算過程計算f。再寫一個函數，通過迭代計算過程計算f。

練習1.12 下面的數值模式稱為帕斯卡三角形：

三角形兩個斜邊上的數都是1，內部的每個數是位于它上面的兩個數之和[33]。請寫一個函數，它通過一個遞歸計算過程計算帕斯卡三角形。

練習1.13 證明Fib（n）是最接近的整數，其中。提示：利用歸納法和斐波那契數的定義（見1.2.2節），證明，其中。