要理解遞歸算法，首先要了解遞歸的內涵。



“遞歸要求我們用新的方式思考原來的問題。”

——戴維·貝茲利（David Beazley）



遞歸令人生畏，它是編程面試中經常提到的高級計算機科學主題。但是遞歸並沒有什麼神奇之處。

本書使用 Python 和 JavaScript 示例講述遞歸的基礎知識，並闡明遞歸算法的基本原理。你將了解何時使用遞歸函數（重要的是，何時不使用它），如何在求職面試中快速實現遞歸算法，如何使用遞歸法解決編程中的難題。



本書主要內容：

1.遞歸函數如何使用調用棧這種數據結構；

2.如何簡化遞歸函數的編寫；

3.如何使用遞歸算法為文件繫統編寫腳本，繪制分形，創建迷宮等；

4.如何通過記憶化尾和調用優化使遞歸算法更高效。



本書化繁為簡，用一種通俗易懂的方式講述遞歸算法。如果你希望精通遞歸算法或者提升編程水平，那麼本書值得閱讀。

目錄



第 1部分理解遞歸

第 1章遞歸 3

1.1如何定義遞歸 3

1.2函數 5

1.3棧 7

1.4調用棧 9

1.5遞歸函數和棧溢出 11

1.6基本情況與遞歸情況 13

1.7位於遞歸調用之前與之後的代碼 15

1.8小結 18

延伸閱讀 18

練習題 18

第 2章遞歸與迭代 20

2.1計算階乘 20

2.1.1迭代式的階乘算法 21

2.1.2遞歸式的階乘算法 21

2.1.3用遞歸計算階乘為什麼很不合適23

2.2計算斐波那契數列 24

2.2.1用迭代法計算斐波那契數列 24

2.2.2用遞歸法計算斐波那契數列 25

2.2.3用遞歸法計算斐波那契數列為什麼很不合適 27

2.3把遞歸算法轉換成迭代算法 27

2.4把迭代算法轉換成遞歸算法 29

2.5案例研究：指數運算 32

2.5.1用遞歸函數實現指數運算 33

2.5.2用遞歸算法的思路實現迭代式的指數計算函數 34

2.6在什麼場合下需要使用遞歸 37

2.7如何編寫遞歸算法 39

2.8小結 39

延伸閱讀 40

練習題 40

實踐項目 40

第3章經典的遞歸算法 42

3.1求數素之和 42

3.2反轉字符串 45

3.3判斷某字符串是否為回文 48

3.4漢諾塔問題 50

3.5洪泛填充算法 56

3.6阿克曼函數 60

3.7小結 62

延伸閱讀 63

練習題 63

實踐項目 63

第4章回溯與樹的遍歷算法 65

4.1樹的遍歷 65

4.1.1Python 與 JavaScript 中的樹狀數據結構 66

4.1.2遍歷樹狀結構 68

4.1.3樹的先序遍歷 68

4.1.4樹的後序遍歷 70

4.1.5樹的中序遍歷 71

4.2在樹中尋找由 8 個字母構成的名字 72

4.3計算樹的深度 74

4.4走迷宮 76

4.5小結 83

延伸閱讀 84

練習題 84

實踐項目 85

第5章分治算法 86

5.1二分搜索 86

5.2快速排序 89

5.3歸並排序 96

5.4求數組中各整數之和 103

5.5卡拉楚巴乘法 104

5.6卡拉楚巴算法背後的數學原理 109

5.7小結 110

延伸閱讀 111

練習題 112

實踐項目 112

第6章排列與組合 114

6.1集合論的術語 114

6.2如何尋找每一種素的排列 117

6.3用多層循環獲取各種排列方式 120

6.4編寫密碼破解器 122

6.5通過遞歸計算 k組合 125

6.6獲取各種正確的括號匹配形式 130

6.7冪集 134

6.8小結 137

延伸閱讀 138

練習題 138

實踐項目 139

第7章記憶化與動態規劃 140

7.1記憶化 140

7.1.1自上而下的動態規劃 140

7.1.2函數式編程中的記憶化 141

7.1.3對遞歸式的斐波那契算法做記憶化處理 143

7.2Python 的 functools 模塊 146

7.3對非純函數做記憶化會怎樣 147

7.4小結 148

延伸閱讀 148

練習題 149

第8章尾調用優化 150

8.1尾遞歸與尾調用優化的原理 150

8.2如何通過累加器參數做尾遞歸 152

8.3尾遞歸的局限 153

8.4尾遞歸案例研究 154

8.4.1用尾遞歸反轉字符串 154

8.4.2用尾遞歸尋找子字符串 155

8.4.3用尾遞歸做指數運算 156

8.4.4用尾遞歸判斷某數是奇數

還是偶數 156

8.5小結 158

延伸閱讀 159

練習題 159

第9章繪制分形 160

9.1海龜繪圖 160

9.2基本的海龜函數 162

9.3謝爾賓斯基三角形 163

9.4謝爾賓斯基地毯 167

9.5分形樹 170

9.6科赫曲線及科赫雪花 174

9.7希爾伯特曲線 176

9.8小結 179

延伸閱讀 179

練習題 180

實踐項目 180

第 2部分項目

第 10章文件查找器 185

10.1文件搜索程序的完整代碼 185

10.2用匹配函數來表示特定的搜索

標準 186

10.2.1尋找偶數字節的文件 187

10.2.2尋找名稱包音字母的文件 188

10.3用遞歸式的 walk()函數走查

文件夾 188

10.4用特定的匹配函數調用 walk() 函數以執行搜索 190

10.5用 Python 標準庫中的函數處理 文件 191

10.5.1尋找與文件名有關的信息 191

10.5.2尋找與文件的時間戳有關的信息 192

10.5.3修改文件 194

10.6小結 195

延伸閱讀 195

第 11章迷宮生成器 196

11.1完整的迷宮生成程序 196

11.2設定迷宮生成器所使用的常量 201

11.3創建表示迷宮的數據結構 202

11.4輸出表示迷宮的數據結構 203

11.5用遞歸回溯算法在迷宮中挖路 204

11.6觸發遞歸調用鏈 208

11.7小結 209

延伸閱讀 209

第 12章解決滑塊拼圖問題 210

12.1遞歸地解決15滑塊拼圖問題 210

12.2完整的滑塊拼圖解決程序 212

12.3設定程序需要使用的常量 220

12.4用適當的數據結構表示滑塊拼圖的狀態 221

12.4.1顯示拼圖 221

12.4.2創建一個新的數據結構 222

12.4.3尋找拼圖中的空白格子所在的位置 223

12.4.4移動滑塊 223

12.4.5撤銷某次移動 225

12.5設定新的拼圖謎題 225

12.6遞歸地解決滑塊拼圖謎題 228

12.6.1用 solve()函數觸發算法並演示算法給出的答案 229

12.6.2在 attemptMove()函數中實現核心算法 230

12.7反復啟動 solve()函數並逐漸

放寬步數限制 233

12.8小結 235

延伸閱讀 235

第 13章分形圖案制作器 236

13.1程序內置的幾種分形 236

13.2分形圖案制作器程序所采用的算法 238

13.3分形圖案制作器程序的完整代碼 240

13.4設定常量並配置海龜的參數 243

13.5編寫圖形繪制函數 244

13.5.1drawFilledSquare()函數 245

13.5.2drawTriangleOutline()函數 247

13.6在遞歸過程中反復執行圖形繪制函數 248

13.6.1準備工作 249

13.6.2解析字典之中的遞歸規則 250

13.6.3根據字典所描述的規則執行遞歸 252

13.7設計遞歸的規則與參數 254

13.7.1四角分形 254

13.7.2螺旋方塊 255

13.7.3雙螺旋方塊 255

13.7.4三角螺旋 255

13.7.5康威生命遊戲的滑翔機 256

13.7.6謝爾賓斯基三角形 256

13.7.7波浪 257

13.7.8號角 257

13.7.9雪花 258

13.7.10作為基本圖形的正方形或等邊三角形 259

13.8自己設計分形 259

13.9小結 260

延伸閱讀 261

第 14章畫中畫制作器 262

14.1安裝 Pillow 庫 262

14.2把基本圖像準備好 263

14.3畫中畫制作器程序的完整代碼 265

14.4在執行遞歸替換之前先做一些準備工作 266

14.5尋找有品紅色像素出現的矩形區域 268

14.6縮小基本圖像 269

14.7遞歸地替換圖中的品紅色像素 272

14.8小結 274

延伸閱讀 274