遞歸
遞歸的含義：任何調用自身的函數稱為遞歸。用遞歸求解問題要點在于遞歸函數調用自身取解決一個規(guī)模比原始問題小一些的問題，這個過程稱為遞歸步驟。遞歸步驟會導致更多的遞歸調用，因此保證遞歸過程能夠正確終止是很重要的。每次函數都會用比原問題規(guī)模更小的問題來調用自身，問題會隨著規(guī)模不斷變小必然能收斂到基本情形。
遞歸的意義：遞歸代碼通常是比迭代代碼更加簡潔易懂的。一般來說，在編譯或解釋時，循環(huán)會轉化為遞歸函數。當任務能被相似的子任務定義時，使用遞歸處理十分有效。例如排序，搜索，遍歷等問題往往有簡潔的遞歸解決方案。
遞歸的格式：遞歸函數在執(zhí)行一個任務時，需要調用函數自身來完成一些子任務。而有時，函數不需要繼續(xù)調用函數自身就可以完成當前子任務，此時這種情況我們稱為基本情形，而需要調用自身來完成子任務的情況稱為遞歸情形，如下所示
image.png
遞歸和迭代的比較：
對于遞歸來說，其特點如下：
- 到達基本情形時，遞歸終止
- 遞歸調用需要額外的空間用于棧幀(內存)開銷
- 如果出現無窮遞歸，程序可能會耗盡內存，并出現棧溢出
- 有些問題用遞歸的方式更易解答
迭代的特點如下：
- 循環(huán)條件為false時，迭代終止
- 每次迭代不需要額外的內存開銷
- 由于沒有額外的內存開銷，所以當出現死循環(huán)時，程序會一直循環(huán)執(zhí)行
- 采用迭代求解問題可能不如遞歸解決方案那樣顯而易見
總結：
- 遞歸算法有兩類情形：基本情形和遞歸情形
- 每個遞歸函數必須終止于基本情形
- 通常，迭代解決方案比遞歸解決方案更加有效（因為后者需要額外的函數調用開銷）
- 迭代算法通常是可以用遞歸算法來替換的，而有些遞歸算法并不能用迭代求解
遞歸算法的經典用例：
- 斐波那契數列，階乘
- 歸并排序，快速排序
- 二分查找
- 樹的遍歷（前中后序遍歷）及很多樹相關問題
- 圖的遍歷（深度優(yōu)先，廣度優(yōu)先搜索）
- 動態(tài)規(guī)劃
- 分治算法
- 漢諾塔問題
- 回溯算法
遞歸的問題示例：
image.png
進階的問題參見具體數學第一章內容
image.png
回溯
回溯的定義：回溯是一種采用分治策略進行窮舉搜索的方法
- 有時求解一個問題最好的算法是嘗試所有可能性
- 這種方式通常很慢，但通過一些工具能輔助該過程
- 工具：生成基本對象的算法，如二進制串(
位二進制串有
種可能性)，排列(
)，組合(
)，一般字符串(長度為
進制串有
種可能性)等
- 通過剪枝回溯可以加速窮舉搜索
回溯算法的經典用例：
- 二進制串：產生所有的二進制串
- 生成
- 背包問題
- 廣義字符串
- 哈密頓回路
- 圖著色問題
回溯的問題示例：
image.png
image.png
本章只是起到一個引導作用，更多詳細內容在后續(xù)章節(jié)會詳細介紹
