遞歸
遞歸的含義：任何調(diào)用自身的函數(shù)稱為遞歸篮灼。用遞歸求解問(wèn)題要點(diǎn)在于遞歸函數(shù)調(diào)用自身取解決一個(gè)規(guī)模比原始問(wèn)題小一些的問(wèn)題，這個(gè)過(guò)程稱為遞歸步驟。遞歸步驟會(huì)導(dǎo)致更多的遞歸調(diào)用浇坐，因此保證遞歸過(guò)程能夠正確終止是很重要的。每次函數(shù)都會(huì)用比原問(wèn)題規(guī)模更小的問(wèn)題來(lái)調(diào)用自身黔宛，問(wèn)題會(huì)隨著規(guī)模不斷變小必然能收斂到基本情形近刘。
遞歸的意義：遞歸代碼通常是比迭代代碼更加簡(jiǎn)潔易懂的。一般來(lái)說(shuō)臀晃，在編譯或解釋時(shí)觉渴，循環(huán)會(huì)轉(zhuǎn)化為遞歸函數(shù)。當(dāng)任務(wù)能被相似的子任務(wù)定義時(shí)徽惋，使用遞歸處理十分有效案淋。例如排序，搜索险绘，遍歷等問(wèn)題往往有簡(jiǎn)潔的遞歸解決方案踢京。
遞歸的格式：遞歸函數(shù)在執(zhí)行一個(gè)任務(wù)時(shí)，需要調(diào)用函數(shù)自身來(lái)完成一些子任務(wù)宦棺。而有時(shí)瓣距，函數(shù)不需要繼續(xù)調(diào)用函數(shù)自身就可以完成當(dāng)前子任務(wù)，此時(shí)這種情況我們稱為基本情形渺氧，而需要調(diào)用自身來(lái)完成子任務(wù)的情況稱為遞歸情形旨涝，如下所示
遞歸和迭代的比較：
對(duì)于遞歸來(lái)說(shuō)，其特點(diǎn)如下：
- 到達(dá)基本情形時(shí)侣背，遞歸終止
- 遞歸調(diào)用需要額外的空間用于棧幀(內(nèi)存)開(kāi)銷
- 如果出現(xiàn)無(wú)窮遞歸白华，程序可能會(huì)耗盡內(nèi)存，并出現(xiàn)棧溢出
- 有些問(wèn)題用遞歸的方式更易解答
迭代的特點(diǎn)如下：
- 循環(huán)條件為false時(shí)贩耐，迭代終止
- 每次迭代不需要額外的內(nèi)存開(kāi)銷
- 由于沒(méi)有額外的內(nèi)存開(kāi)銷弧腥，所以當(dāng)出現(xiàn)死循環(huán)時(shí)，程序會(huì)一直循環(huán)執(zhí)行
- 采用迭代求解問(wèn)題可能不如遞歸解決方案那樣顯而易見(jiàn)
總結(jié)：
- 遞歸算法有兩類情形：基本情形和遞歸情形
- 每個(gè)遞歸函數(shù)必須終止于基本情形
- 通常潮太，迭代解決方案比遞歸解決方案更加有效（因?yàn)楹笳咝枰~外的函數(shù)調(diào)用開(kāi)銷）
- 迭代算法通常是可以用遞歸算法來(lái)替換的管搪，而有些遞歸算法并不能用迭代求解
遞歸算法的經(jīng)典用例：
- 斐波那契數(shù)列虾攻，階乘
- 歸并排序，快速排序
- 二分查找
- 樹(shù)的遍歷（前中后序遍歷）及很多樹(shù)相關(guān)問(wèn)題
- 圖的遍歷（深度優(yōu)先更鲁，廣度優(yōu)先搜索）
- 動(dòng)態(tài)規(guī)劃
- 分治算法
- 漢諾塔問(wèn)題
- 回溯算法
遞歸的問(wèn)題示例：
進(jìn)階的問(wèn)題參見(jiàn)具體數(shù)學(xué)第一章內(nèi)容
回溯
回溯的定義：回溯是一種采用分治策略進(jìn)行窮舉搜索的方法
- 有時(shí)求解一個(gè)問(wèn)題最好的算法是嘗試所有可能性
- 這種方式通常很慢霎箍，但通過(guò)一些工具能輔助該過(guò)程
- 工具：生成基本對(duì)象的算法，如二進(jìn)制串(
位二進(jìn)制串有
種可能性)澡为，排列(
)漂坏，組合(
)，一般字符串(長(zhǎng)度為
進(jìn)制串有
種可能性)等
- 通過(guò)剪枝回溯可以加速窮舉搜索
回溯算法的經(jīng)典用例：
- 二進(jìn)制串：產(chǎn)生所有的二進(jìn)制串
- 生成
- 背包問(wèn)題
- 廣義字符串
- 哈密頓回路
- 圖著色問(wèn)題
回溯的問(wèn)題示例：
本章只是起到一個(gè)引導(dǎo)作用媒至，更多詳細(xì)內(nèi)容在后續(xù)章節(jié)會(huì)詳細(xì)介紹
