遞歸算法與項目實戰(zhàn)

目　　錄

第 1部分　理解遞歸
第 1章　遞歸 3
1.1　如何定義遞歸 3
1.2　函數(shù) 5
1.3　棧 7
1.4　調(diào)用棧 9
1.5　遞歸函數(shù)和棧溢出 11
1.6　基本情況與遞歸情況 13
1.7　位于遞歸調(diào)用之前與之后的代碼 15
1.8　小結(jié) 18
延伸閱讀 18
練習(xí)題 18
第 2章　遞歸與迭代 20
2.1　計算階乘 20
2.1.1　迭代式的階乘算法 21
2.1.2　遞歸式的階乘算法 21
2.1.3　用遞歸計算階乘為什么很不合適23
2.2　計算斐波那契數(shù)列 24
2.2.1　用迭代法計算斐波那契數(shù)列 24
2.2.2　用遞歸法計算斐波那契數(shù)列 25
2.2.3　用遞歸法計算斐波那契數(shù)列為什么很不合適 27
2.3　把遞歸算法轉(zhuǎn)換成迭代算法 27
2.4　把迭代算法轉(zhuǎn)換成遞歸算法 29
2.5　案例研究：指數(shù)運算 32
2.5.1　用遞歸函數(shù)實現(xiàn)指數(shù)運算 33
2.5.2　用遞歸算法的思路實現(xiàn)迭代式的指數(shù)計算函數(shù) 34
2.6　在什么場合下需要使用遞歸 37
2.7　如何編寫遞歸算法 39
2.8　小結(jié) 39
延伸閱讀 40
練習(xí)題 40
實踐項目 40
第3章　經(jīng)典的遞歸算法 42
3.1　求數(shù)組中各元素之和 42
3.2　反轉(zhuǎn)字符串 45
3.3　判斷某字符串是否為回文 48
3.4　漢諾塔問題 50
3.5　洪泛填充算法 56
3.6　阿克曼函數(shù) 60
3.7　小結(jié) 62
延伸閱讀 63
練習(xí)題 63
實踐項目 63
第4章　回溯與樹的遍歷算法 65
4.1　樹的遍歷 65
4.1.1　Python 與 JavaScript 中的樹狀數(shù)據(jù)結(jié)構(gòu) 66
4.1.2　遍歷樹狀結(jié)構(gòu) 68
4.1.3　樹的先序遍歷 68
4.1.4　樹的后序遍歷 70
4.1.5　樹的中序遍歷 71
4.2　在樹中尋找由 8 個字母構(gòu)成的名字 72
4.3　計算樹的深度 74
4.4　走迷宮 76
4.5　小結(jié) 83
延伸閱讀 84
練習(xí)題 84
實踐項目 85
第5章　分治算法 86
5.1　二分搜索 86
5.2　快速排序 89
5.3　歸并排序 96
5.4　求數(shù)組中各整數(shù)之和 103
5.5　卡拉楚巴乘法 104
5.6　卡拉楚巴算法背后的數(shù)學(xué)原理 109
5.7　小結(jié) 110
延伸閱讀 111
練習(xí)題 112
實踐項目 112
第6章　排列與組合 114
6.1　集合論的術(shù)語 114
6.2　如何尋找每一種無重復(fù)元素的排列 117
6.3　用多層循環(huán)獲取各種排列方式 120
6.4　編寫密碼破解器 122
6.5　通過遞歸計算 k組合 125
6.6　獲取各種正確的括號匹配形式 130
6.7　冪集 134
6.8　小結(jié) 137
延伸閱讀 138
練習(xí)題 138
實踐項目 139
第7章　記憶化與動態(tài)規(guī)劃 140
7.1　記憶化 140
7.1.1　自上而下的動態(tài)規(guī)劃 140
7.1.2　函數(shù)式編程中的記憶化 141
7.1.3　對遞歸式的斐波那契算法做記憶化處理 143
7.2　Python 的 functools 模塊 146
7.3　對非純函數(shù)做記憶化會怎樣 147
7.4　小結(jié) 148
延伸閱讀 148
練習(xí)題 149
第8章　尾調(diào)用優(yōu)化 150
8.1　尾遞歸與尾調(diào)用優(yōu)化的原理 150
8.2　如何通過累加器參數(shù)做尾遞歸 152
8.3　尾遞歸的局限 153
8.4　尾遞歸案例研究 154
8.4.1　用尾遞歸反轉(zhuǎn)字符串 154
8.4.2　用尾遞歸尋找子字符串 155
8.4.3　用尾遞歸做指數(shù)運算 156
8.4.4　用尾遞歸判斷某數(shù)是奇數(shù)
還是偶數(shù) 156
8.5　小結(jié) 158
延伸閱讀 159
練習(xí)題 159
第9章　繪制分形 160
9.1　海龜繪圖 160
9.2　基本的海龜函數(shù) 162
9.3　謝爾賓斯基三角形 163
9.4　謝爾賓斯基地毯 167
9.5　分形樹 170
9.6　科赫曲線及科赫雪花 174
9.7　希爾伯特曲線 176
9.8　小結(jié) 179
延伸閱讀 179
練習(xí)題 180
實踐項目 180
第 2部分　項目
第 10章　文件查找器 185
10.1　文件搜索程序的完整代碼 185
10.2　用匹配函數(shù)來表示特定的搜索
標(biāo)準 186
10.2.1　尋找偶數(shù)字節(jié)的文件 187
10.2.2　尋找名稱包含所有元音字母的文件 188
10.3　用遞歸式的 walk()函數(shù)走查
文件夾 188
10.4　用特定的匹配函數(shù)調(diào)用 walk() 函數(shù)以執(zhí)行搜索 190
10.5　用 Python 標(biāo)準庫中的函數(shù)處理 文件 191
10.5.1　尋找與文件名有關(guān)的信息 191
10.5.2　尋找與文件的時間戳有關(guān)的信息 192
10.5.3　修改文件 194
10.6　小結(jié) 195
延伸閱讀 195
第 11章　迷宮生成器 196
11.1　完整的迷宮生成程序 196
11.2　設(shè)定迷宮生成器所使用的常量 201
11.3　創(chuàng)建表示迷宮的數(shù)據(jù)結(jié)構(gòu) 202
11.4　輸出表示迷宮的數(shù)據(jù)結(jié)構(gòu) 203
11.5　用遞歸回溯算法在迷宮中挖路 204
11.6　觸發(fā)遞歸調(diào)用鏈 208
11.7　小結(jié) 209
延伸閱讀 209
第 12章　解決滑塊拼圖問題 210
12.1　遞歸地解決15滑塊拼圖問題 210
12.2　完整的滑塊拼圖解決程序 212
12.3　設(shè)定程序需要使用的常量 220
12.4　用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表示滑塊拼圖的狀態(tài) 221
12.4.1　顯示拼圖 221
12.4.2　創(chuàng)建一個新的數(shù)據(jù)結(jié)構(gòu) 222
12.4.3　尋找拼圖中的空白格子所在的位置 223
12.4.4　移動滑塊 223
12.4.5　撤銷某次移動 225
12.5　設(shè)定新的拼圖謎題 225
12.6　遞歸地解決滑塊拼圖謎題 228
12.6.1　用 solve()函數(shù)觸發(fā)算法并演示算法給出的答案 229
12.6.2　在 attemptMove()函數(shù)中實現(xiàn)核心算法 230
12.7　反復(fù)啟動 solve()函數(shù)并逐漸
放寬步數(shù)限制 233
12.8　小結(jié) 235
延伸閱讀 235
第 13章　分形圖案制作器 236
13.1　程序內(nèi)置的幾種分形 236
13.2　分形圖案制作器程序所采用的算法 238
13.3　分形圖案制作器程序的完整代碼 240
13.4　設(shè)定常量并配置海龜?shù)膮?shù) 243
13.5　編寫圖形繪制函數(shù) 244
13.5.1　drawFilledSquare()函數(shù) 245
13.5.2　drawTriangleOutline()函數(shù) 247
13.6　在遞歸過程中反復(fù)執(zhí)行圖形繪制函數(shù) 248
13.6.1　準備工作 249
13.6.2　解析字典之中的遞歸規(guī)則 250
13.6.3　根據(jù)字典所描述的規(guī)則執(zhí)行遞歸 252
13.7　設(shè)計遞歸的規(guī)則與參數(shù) 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　自己設(shè)計分形 259
13.9　小結(jié) 260
延伸閱讀 261
第 14章　畫中畫制作器 262
14.1　安裝 Pillow 庫 262
14.2　把基本圖像準備好 263
14.3　畫中畫制作器程序的完整代碼 265
14.4　在執(zhí)行遞歸替換之前先做一些準備工作 266
14.5　尋找有品紅色像素出現(xiàn)的矩形區(qū)域 268
14.6　縮小基本圖像 269
14.7　遞歸地替換圖中的品紅色像素 272
14.8　小結(jié) 274
延伸閱讀 274