引導

????????遞歸算法算是我們比較常用的一種算法。但是想用好并不簡單。本章我不再介紹簡單的概念，主要講解遞歸算法的優缺點和如何用遞歸寫代碼。

個人愛好

其實相對于使用while循環，我更喜歡使用遞歸算法。為什么呢？

• 使用遞歸算法代碼往往會變得更加簡潔，特別當其他人使用while，for等幾十行代碼實現功能，而你僅僅需要幾行代碼。就特別有一種自豪感。

• 遞歸算法，我覺得對思維的邏輯性要求更高，遞歸算法常常會把人帶入思維誤區，腦袋一場混雜
  以上是我個人喜歡使用遞歸的主要原因。

但是遞歸算法也存在很多的弊端:

1. 棧溢出。我們知道函數參數和局部變量都是保存在棧中的，并且每個線程的棧空間默認大小為8M。
2. 空間復雜度高。和棧溢出的道理一樣
3. 重復計算。這個要視具體的問題了，可能會出現重復計算的現象
4. 過多的函數調用會耗時較多。我們知道函數調用的過程會有額外的時間消耗在上下文保存中。當遞歸層次很深的時候，就會是一個很客觀的時間消耗。

如何解決這些弊端？

其中1，3，4我們可以通過控制的遞歸層次來進行控制，如：

int deep = 0； f(n) { ??? deep++; ??? / *規定最多遞歸100層* / ??? if(deep > 100) ??? { ??????? return; ??? } ??? f(n-1); }

????????關于重復計算，我們可以通過使用hash表來進行處理。將f(m)的結果進行hash保存，在處理f(n)時，現在hash表中查看是否存在該value。

如何使用遞歸？

????????遞歸說簡單也簡單，說難也很難。簡單就是將問題能夠分為子問題和找到終止條件即可。困難在于如何從一個具體的問題中，分析出這兩個條件。

????????比如教科書上利用遞歸計算階乘值，這些很簡單。因為你能夠很容易分析出問題分為子問題和終止條件。

????????但是如果你要使用遞歸處理下面的問題，你可以很快的給出結果嗎？合并兩條有序鏈表。可以在鏈表練習題中找點思路。【追求卓越03】數據結構--鏈表練習題-CSDN博客

????????其實，我覺得想要熟練掌握好遞歸，你要多練，多做題，多思考。這樣你才能對一個具體的問題，分析出遞歸公式以及終止條件。

????????僅僅通過他人三言兩語給你分析，你是很難得到進步。別人能夠很快的分析出來，那是人家經過了大量的練習。這點要注意哦！！！

總結

????????本節，我們主要介紹了大家熟知的遞歸算法以及它存在的一些問題：棧溢出，空間復雜度高，函數調用耗時多，以及對應的解決方式。

????????寫遞歸的方式：找到遞歸公式和終止條件。再轉化為代碼。并且只有大量練習，才能熟練掌握遞歸算法。