目　　錄 第 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　計(jì)算階乘 20 2.1.1　迭代式的階乘算法 21 2.1.2　遞歸式的階乘算法 21 2.1.3　用遞歸計(jì)算階乘為什么很不合適23 2.2　計(jì)算斐波那契數(shù)列 24 2.2.1　用迭代法計(jì)算斐波那契數(shù)列 24 2.2.2　用遞歸法計(jì)算斐波那契數(shù)列 25 2.2.3　用遞歸法計(jì)算斐波那契數(shù)列為什么很不合適 27 2.3　把遞歸算法轉(zhuǎn)換成迭代算法 27 2.4　把迭代算法轉(zhuǎn)換成遞歸算法 29 2.5　案例研究：指數(shù)運(yùn)算 32 2.5.1　用遞歸函數(shù)實(shí)現(xiàn)指數(shù)運(yùn)算 33 2.5.2　用遞歸算法的思路實(shí)現(xiàn)迭代式的指數(shù)計(jì)算函數(shù) 34 2.6　在什么場合下需要使用遞歸 37 2.7　如何編寫遞歸算法 39 2.8　小結(jié) 39 延伸閱讀 40 練習(xí)題 40 實(shí)踐項(xiàng)目 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 實(shí)踐項(xiàng)目 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　計(jì)算樹的深度 74 4.4　走迷宮 76 4.5　小結(jié) 83 延伸閱讀 84 練習(xí)題 84 實(shí)踐項(xiàng)目 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 實(shí)踐項(xiàng)目 112 第6章　排列與組合 114 6.1　集合論的術(shù)語 114 6.2　如何尋找每一種無重復(fù)元素的排列 117 6.3　用多層循環(huán)獲取各種排列方式 120 6.4　編寫密碼破解器 122 6.5　通過遞歸計(jì)算 k組合 125 6.6　獲取各種正確的括號匹配形式 130 6.7　冪集 134 6.8　小結(jié) 137 延伸閱讀 138 練習(xí)題 138 實(shí)踐項(xiàng)目 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ù)運(yùn)算 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 實(shí)踐項(xiàng)目 180 第 2部分　項(xiàng)目 第 10章　文件查找器 185 10.1　文件搜索程序的完整代碼 185 10.2　用匹配函數(shù)來表示特定的搜索 標(biāo)準(zhǔn) 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)準(zhǔn)庫中的函數(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ù)中實(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　準(zhǔn)備工作 249 13.6.2　解析字典之中的遞歸規(guī)則 250 13.6.3　根據(jù)字典所描述的規(guī)則執(zhí)行遞歸 252 13.7　設(shè)計(jì)遞歸的規(guī)則與參數(shù) 254 13.7.1　四角分形 254 13.7.2　螺旋方塊 255 13.7.3　雙螺旋方塊 255 13.7.4　三角螺旋 255 13.7.5　康威生命游戲的滑翔機(jī) 256 13.7.6　謝爾賓斯基三角形 256 13.7.7　波浪 257 13.7.8　號角 257 13.7.9　雪花 258 13.7.10　作為基本圖形的正方形或等邊三角形 259 13.8　自己設(shè)計(jì)分形 259 13.9　小結(jié) 260 延伸閱讀 261 第 14章　畫中畫制作器 262 14.1　安裝 Pillow 庫 262 14.2　把基本圖像準(zhǔn)備好 263 14.3　畫中畫制作器程序的完整代碼 265 14.4　在執(zhí)行遞歸替換之前先做一些準(zhǔn)備工作 266 14.5　尋找有品紅色像素出現(xiàn)的矩形區(qū)域 268 14.6　縮小基本圖像 269 14.7　遞歸地替換圖中的品紅色像素 272 14.8　小結(jié) 274 延伸閱讀 274