递归算法与项目实战

图书标准信息

• 作者 [美]阿尔·斯维加特（Al Sweigart）
• 出版社 人民邮电出版社
• 出版时间 2023-11
• 版次 1
• ISBN 9787115616760
• 定价 99.80元
• 装帧 平装
• 开本 16开
• 页数 274页
• 字数 445千字

【内容简介】

本书凝聚了作者多年的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