一、初識遞歸
1、遞歸的定義？遞歸是算法思想或者算法策略嗎？
-
遞歸的定義：函數(shù)（方法）直接或者間接調(diào)用自身。 - 嚴格來講遞歸不是算法思想或者算法策略，只是一種常用的編程技巧。
image.png
2、生活中一些有趣的遞歸現(xiàn)象，好好品，加深理解。
image.png
3、自己手動繪制下面函數(shù)?？臻g建立和釋放的過程（多感悟下?？臻g）？
image.png
image.png
4、遞歸調(diào)用如果沒有邊界條件，會出現(xiàn)什么問題？
- 如果遞歸調(diào)用沒有終止條件，將會一直消耗?？臻g。最終導致棧內(nèi)存溢出（Stack Overflow）
5、遞歸一定是最優(yōu)解嗎？如果不一定是，那么遞歸有什么好處？
- 遞歸求出來的很可能不是最優(yōu)解，也可能是最優(yōu)解。
- 遞歸不是為了求得最優(yōu)解，是為了簡化解決問題的思路，代碼會更加簡潔
image.png
6、遞歸的基本思想（重要的思想）？
拆解問題- 把規(guī)模大的問題變成規(guī)模較小的
同類問題 - 規(guī)模較小的問題又不斷變成規(guī)模更小的同類問題
- 規(guī)模小到一定程度就可以直接得出它的解
求解- 由最小規(guī)模問題的解得出較大規(guī)模問題的解
- 由較大規(guī)模問題的解不斷得出規(guī)模更大問題的解
- 最后得出原來問題的解
image.png
7、為什么鏈表、二叉樹的很多相關問題，都可以嘗試使用遞歸？
- 因為鏈表、二叉樹本身就是遞歸的結(jié)構（鏈表中包含鏈表、二叉樹中包含二叉樹）
8、遞歸的使用套路（本章最重要）？
- ①明確函數(shù)功能
- 先不要去思考代碼里面怎么寫，首先搞清楚這個函數(shù)是干嘛用的，能完成什么功能？
- ②明確原來問題與子問題
- 尋找 f(n) 與 f(n-1)的關系
- ③明確遞歸基（邊界條件）
- 遞歸的過程中，子問題的規(guī)模在不斷減小，當小到一定程度時可以直接得出它的解
- 尋找遞歸基，相當于是思考：問題規(guī)模小到什么程度可以直接得出解？
二、經(jīng)典遞歸問題：斐波那契數(shù)列的故事
1、什么是斐波那契數(shù)列？
image.png
2、為什么時間復雜度是 O(2^n)？
- 如下圖所示，每次調(diào)用，數(shù)據(jù)函數(shù)規(guī)模都是原來的兩倍
- 每個函數(shù)里面都需要執(zhí)行一個加法
- 所以綜合來說，時間復雜度就是 O(2^n)，這個時間復雜度是非?？植赖??
image.png
3、遞歸函數(shù)的空間復雜度怎么計算？為什么斐波那契數(shù)列的空間復雜度是 O(n)?
- 基礎認知：遞歸調(diào)用的空間復雜度 = 每一次調(diào)用函數(shù)的輔助空間 * 遞歸最大深度
- 把握最關鍵的信息，在 F(n-1) 計算完畢之前，F(xiàn)(n-2)是不會被執(zhí)行也不會分配?？臻g的。
-
所以上述斐波那契數(shù)列的空間復雜度就是 O(n-1)，去除常數(shù)項，就是 O(n)
image.png
4、使用數(shù)組來存放已經(jīng)計算過的 F(n)，防止重復計算。優(yōu)化第一版如下
image.png
5、去除遞歸調(diào)用。優(yōu)化第二版如下
image.png
6、觀察發(fā)現(xiàn)優(yōu)化第二版其實僅僅使用到數(shù)組中的 2 個元素，所以可以使用滾動數(shù)組來優(yōu)化。優(yōu)化版本三如下
image.png
- 乘、除、模運算效率比較低，建議使用其他方式取代
- 那么 n % 2 ，可以用其他方式取代嗎？
- 注意觀察，其實 n % 2 本質(zhì)上是看 n 的二進制數(shù)據(jù)最低位上是 0 還是 1
- 所以
n % 2等價于n & 1
image.png
7、觀察發(fā)現(xiàn)，就用到數(shù)組兩個元素，其實直接用兩個變量即可啊。優(yōu)化版本四如下
image.png
8、對于斐波那契數(shù)列，后面又研究出了特征方程，優(yōu)化版本五如下（了解即可）？
image.png
