遞歸
什麼是遞歸？首先遞歸是一種廣泛的算法或者程式設計技巧，很多資料結構和算法的實作都依賴遞歸，比如DFS（深度優先周遊），二叉樹的前中後序周遊等等。
示例：舉個簡單的例子，比如排隊，你排在第n個位置，具體n是多少，你不知道，是以你就問你前面一個人：“你是第幾個人？”然而你前面的人也不知道他是第幾個人，是以他就問他前面的人是第幾個人，這樣一直向前問，知道問到第一個人，然後第二個人知道自己是第二然後告訴第三個人，然後第三個人知道自己是第三，然後一直向後面這樣回報，到你這裡，你也就知道自己是第幾個人了，把這個過程抽象成一個算法就是遞歸！去的過程叫做“遞”，回來的過程叫做“歸”，而這個遞歸函數就可以抽象成f(n)=f(n-1)+1，其中，f(1)=1。
遞歸滿足條件：
通過上面那個例子，我們可以了解遞歸到底是什麼，那麼怎麼分析一個問題能否用遞歸來解決呢？
1.一個問題可以分解成幾個子問題。
就比如上面的例子中，想知道第n個位置是多少，可以分解為n的前面一個(n-1)是多少這樣一個子問題。
2.這個問題與分解後的子問題，除了資料規模不同，求解思路一樣就是說我知道了(n-1)位置是多少，我就知道了n的位置是多少。
3.存在遞歸終止條件上面的問題中，我們不可能一直問前面一個人，總會到底一個人的時候，那麼當到了第一個人的時候，即f(1)=1的時候，就是遞歸的終止條件。
練習：
我們在通過一個簡單的例子來了解遞歸，比如n個台階，一次隻能上1步或者2步，問：有多少種走法？這是一道經典的遞歸算法題。
思路解析：首先我們第一步就有兩種解法，一個是1步1個台階，第二個是1步2個台階，當我們走完第一步的時候，那麼我們第二步有幾種走法呢？還是兩種，一步一個台階和一步兩個台階，是以我們能推導出
f(n)=f(n-1)+f(n-2);
為什麼是f(n-1)和f(n-2)？你一步走了1個台階還剩下(n-1)個，同理(n-2)!公式我們推導出來了，子問題也分析完了，那麼終止條件呢？如果最後隻剩下一個台階我們可以一步走完，如果剩下兩個台階也可以一步走完，也可以分兩步走完，如果剩下三個台階就是f(3)= f(2)+f(1)，是以我們定義終止條件是f(2)=2,f(1)=1。是以我們把公式和終止條件放到一起就是：
f(2)=2;
f(1)=1;
f(n)=f(n-1)+f(n-2);
通過這個公式，我們的最終代碼就是：
int f(n){
if(n == 1) return 1;
if(n == 2) return 2;
return f(n-1) + f(n-2);
}
我們平時思考問題的時候總是喜歡，按照線性思考，就是一條流水線似的，思考問題，但是面對遞歸問題，如果也這樣思考，想把遞歸問題平鋪展開，腦子就會一層一層循環的思考下一層怎麼調用，這樣的思維方式是錯誤的，很容易被繞進去，
是以在思考遞歸問題的時候，我們隻需要把遞歸抽象成一個遞歸公式，不用想一層層的調用關系，不用去分解遞歸的每個步驟。 遞歸産生問題： 遞歸代碼可能導緻堆棧溢出，因為函數調用會使用棧來儲存臨時變量，每調用一個函數，都會将臨時變量封裝為棧幀壓入記憶體棧，等函數執行完成傳回時，才出棧。系統棧或者虛拟機棧空間一般記憶體都不大。如果遞歸函數的求解的資料規模很大，調用層次很深，一直壓入棧，就會有堆棧溢出的風險。
遞歸代碼要注意重複計算，這個問題我們用剛才那個上台階的例子解釋，如圖：
從圖中我們可以看到計算f(5)需要計算f(4)和f(3)，但是f(4)和f(3)已經被計算過了，是以會存在一個函數會存在多次重複計算，為了避免重複計算，我們可以通過一個資料結構（比如散清單）來儲存已經進求過解的值，比如f(k)計算過後，存到散清單中，下次在遇到f(k)直接從散清單中取值就行，不需要再計算了，是以上面的代碼可以優化為：
int f(n){
if(n == 1) return 1;
if(n == 2) return 2;
//利用一個map數組存儲key和value，key是n，value是f(n)的結果
if( map.containsKey(n)){
return map.get(n);
}
int res= f(n-1) + f(n-2);
map.put(n,res);
return res;
}
時間複雜度O(n),空間複雜度O(n);
遞歸代碼改為非遞歸代碼實作遞歸代碼好處：表達能力強，寫起來簡潔
遞歸代碼弊端：空間、時間複雜度高，有堆棧溢出的風險，存在重複計算，過多的函數調用比較耗時。
我們先把前面示例中的f(n)=f(n-1) +1代碼改寫：
//遞歸寫法
public int f1(int n){
if(n == 1){
return 1;
}
return f1(n-1)+1;
}
//非遞歸寫法
public int f1(int n){
int ret = 1;
for(int i=2;i<=n;i++){
ret= ret+1;
}
return ret;
}
同樣第二個練習題同樣改寫為：
public int f3(int n){
if (n == 1) return 1;
if (n == 2) return 2;
int ret = 0;
int pre = 1;
int next = 2;
for(int i=3;i<=n;i++){
ret = pre + next;
pre=next;
next=ret;
}
return ret;
}
這裡讀者直接看代碼，可能會一臉懵逼，是以我給解釋一下：
ret用來儲存最終的傳回值。
pre用來定義每次計算的前一個值。
next表示用來計算的後一個值。
我們來用
上台階的那張圖充分解釋一下這幾個值的含義：比如當我們要計算f(3)的結果，那麼從圖中可以看，我們需要知道f(1)和f(2)的值，f(1)和f(2)的值我們都已經知道了，是1和2，那麼f(3)就是3，好了我們現在知道了f(3)的值了，那麼我們現在計算f(4)的值怎麼算呢？從圖中我們可以看出就需要知道f(2)和f(3）的值，f(3)我們已經知道了，那麼是不是f(4)也就知道了，然後我們在計算f(5)的值，是不是需要知道f(3)和f(4)的值，f(3)和f(4)我們也都知道了，那麼f(5)的值我們也知道了，同理f(6)、f(7)....f(n)都知道了，那麼映射到代碼怎麼實作呢？
代碼實作：通過定義終态值pre=1和next=2代表f(1)和f(2)的值，然後我們從i周遊到n，第一次周遊我們能得到f(3)的值，就是ret=pre+next，此時的ret就是f(3),那麼接下來我們要求解f(4),需要f(2)就是next和f(3)就是ret，是以我們按照上台階的圖中的順序，将pre = next，将next= ret，然後開始求解i=4，即f(4)的值，f(4)需要f(2)和f(3),那麼此時pre就代表f(2)，next代表f(3)，剛才的（将pre = next，将next= ret）也就是實作這個語句的意思。然後重複pre = next，将next= ret,繼續i=5，直到i=n,就可以求解了。
内 容 小 結
本節我們主要講解了遞歸函數的相關概念，以及一些經典例題，遞歸是面試中經常出現的算法題，隻要掌握遞歸的基本概念，那麼當遇到遞歸問題的時候不至于手足無措，好了，我們下期再見！