递归算法与项目实战

目　　录



第 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