數據結構與算法系列——遞歸

遞歸的理解

在學習數據結構和算法的過程中，遞歸可能是比較難理解的一個知識點，每次都試著用自己的大腦去把一步一步去想清楚，結果最後把自己都繞暈了。

我們很多人都遇到過這種情況，讀源碼的時候，我們想弄清楚一個方法的具體實現，然後跟進去發現裡邊還有一個方法，然後我們又跟到新的方法裡邊，結果發現裡邊還有另一個新的方法……這樣跟了一層又一層，終於到了最後一層沒有再調用其他的方法，然後我們再一層一層返回去，最終弄明白了最初想了解的方法的作用（實際中這種方式是不推薦的，因為嵌套很多層，最後搞得頭都大了，卻忘記了最初是要幹什麼）。其實這就是一個遞歸的過程，通過一層一層的去了解方法的作用，然後到最後再一層一層返回去，明白最初方法的作用。

到這裡，我想大家其實對遞歸也有一定了解了。其實遞歸就是可以把原來一個大型複雜的任務，分解成一個或幾個與原任務有相類似求解方法的小任務，然後最後有一個終止條件。

遞歸的條件

由此我們可以總結出幾個使用遞歸需要滿足的條件：

• 一個問題可以分解為一個或幾個子問題

• 子問題和原來問題的求解方式相同，只是規模比原問題小

• 存在終止條件，否則會變成無限循環

舉一個例子

前幾天刷劍指offer題庫，碰到了好多題都可以用遞歸的方法計算。比如其中一個經典的跳臺階問題。

題目描述

一隻青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先後次序不同算不同的結果）。

解題思路

每次跳臺階都有兩個選擇，要麼跳1級，要麼跳2級。只有1級臺階的時候只有跳1級1種跳法，有2級時有每次1級1級跳兩次和直接跳2級兩種跳法，當有3級臺階的時候，我們可以從第2級跳1級到第3級，也可以從第1級跳2級到第3級，所以3級臺階的總跳法，就是1級臺階的總跳法和2級臺階的總跳法的總和，由此我們就發現了一個規律從3級之後的算法為 f(n)=f(n-1)+f(n-2)，發現我們要求得結果符合

斐波那契數列。所以我們想知道 n 級臺階總共有多少跳法，只要將 n-1 的跳法加上 n-2 的跳法就可以了。

代碼實現

public class Solution {
 public int JumpFloor(int target) {
 if(target<3){
 return target;
 }
 return JumpFloor(target - 1) + JumpFloor(target - 2);
 }
}

怎麼使用遞歸

我們現在也對遞歸有一定的瞭解了，那遞歸該怎麼用呢？其實在上邊例子中其實已經給出了答案。首先，我們要通過規律推導出遞歸的公式，然後找到遞歸的終止條件，然後把公式轉化為代碼就很容易了。就比如上邊例子中的解題思路中就是這一過程的實現。

有人覺得遞歸難以理解，可能是走入誤區，就像我一開始舉得讀源碼的例子。一定要在腦子裡把遞歸展開，一層一層去調用，然後一層層的返回，試圖去弄明白每一個過程，這其實就有點鑽牛角尖了，尤其是當一個問題分解成好幾個子問題，然後嵌套層數比較多的時候，我們的大腦是沒辦法把每一個過程都能想出來的。相反計算機卻很擅長這種重複的事情，所以我們沒必要在大腦中去分解每一個步驟，我們只需要找到規律公式和終止條件，剩下的交給計算就行了。

使用遞歸需要注意

在實際程序設計的時候，我們使用遞歸的時候要注意幾個問題。

棧溢出問題

我們都知道函數調用時會用棧來保存臨時變量，每調用一個函數，都會將臨時變量封裝為棧幀壓入內存棧，等函數執行結束才出棧。一般系統棧和虛擬機棧都不是很大，當遞歸嵌套的次數較多的時候，就會有棧溢出的風險。

所以如果遞歸的次數比較小的時候我們可以考慮使用遞歸，否則我們就要考慮其他的方法。

重複計算問題

還是以跳臺階的例子來說明，假如我們要計算 5 級臺階有多少種跳法，我們用我們推導出來公式來計算，f(5)=f(4)+f(3)，然後我們分別要求 f(4)=f(3)+f(2)，f(3)=f(2)+f(1)，我們可以看到在求解 f(5) 的時候我們計算過 f(3)，而在計算 f(4) 的時候我們又計算了一遍 f(3)，同樣 f(2) 也被計算了多次，這就是重複計算的問題。

我們可以用散列表來儲存已經計算過的 f(n)，然後在每次計算的時候先去散列表裡查有沒有被計算過，如果有那麼直接使用；如果沒有那把計算後的值存到散列表中，這樣就能避免重複計算的問題。

我們按這個辦法修改一下上邊例子的代碼。

public class Solution {
 Map<integer> resultMap = new HashMap<integer>();
 public int JumpFloor(int target) {
 if(target < 3){
 return target;
 }
 if(resultMap.containsKey(target)){
 return resultMap.get(target);
 }
 int result = JumpFloor(target - 1) + JumpFloor(target - 2);
 resultMap.put(target, result);
 return result;
 }
}
/<integer>/<integer>

效率問題

由於多層遞歸的嵌套，所以會多次調用函數，當次數達到一定數量的時候，就會有很高的時間成本。在空間複雜度上，因為遞歸每調用一次就會在棧中保存一次現場數據，所以每次都要產生這種額外的開銷。

所以，雖然遞歸的代碼看上去非常簡潔，但是也會有很多問題，我們在實際使用的時候一定要注意遞歸可能會帶來的問題。