遞歸算法與項目實戰 The Recursive Book of Recursion: Ace the Coding Interview with Python and JavaScript (Paperback)

本書凝聚了作者多年的Python教學經驗，內容通俗易懂，旨在剖析遞歸及其本質。本書不僅結合Python程序和 JavaScript 程序講述編程的基礎知識，還講述如何利用遞歸算法計算階乘，計算斐波那契數列，遍歷樹，求解迷宮問題，實現二分搜索，完成快速排序和歸並排序，計算大整數乘法，計算排列和組合，解決八皇後問題等。

本書不僅適合開發人員閱讀，還可供電腦相關專業的師生參考。

阿尔·斯维加特（Al Sweigart ）是一名软件开发人员，是 Python 软件基金会的成员，并且是 No Starch出版社的多本编程书的作者。Python是他喜欢的语言，他开发了Python的几个开源模块 。

目　　錄

 

第 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.1　Python 與 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.2　Python 的 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.1　drawFilledSquare()函數 245

13.5.2　drawTriangleOutline()函數 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