详情
本书凝聚了作者多年的Python教学经验，内容通俗易懂，旨在剖析递归及其本质。本书不仅结合Python程序和 JavaScript 程序讲述编程的基础知识，还讲述如何利用递归算法计算阶乘，计算斐波那契数列，遍历树，求解迷宫问题，实现二分搜索，完成快速排序和归并排序，计算大整数乘法，计算排列和组合，解决八皇后问题等。
本书不仅适合开发人员阅读，还可供计算机相关专业的师生参考。
书名：递归算法与项目实战：基于Python与JavaScript
ISBN：978-7-115-61676-0
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 ［美］阿尔•斯维加特（Al Sweigart）
译 爱飞翔
责任编辑 谢晓芳
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书凝聚了作者多年的Python教学经验，内容通俗易懂，旨在剖析递归及其本质。本书不仅结合Python程序和 JavaScript 程序讲述编程的基础知识，还讲述如何利用递归算法计算阶乘，计算斐波那契数列，遍历树，求解迷宫问题，实现二分搜索，完成快速排序和归并排序，计算大整数乘法，计算排列和组合，解决八皇后问题等。
本书不仅适合开发人员阅读，还可供计算机相关专业的师生参考。
Al联系我给本书写一篇序，我看到书的内容后，相当激动，这竟然是一本讲递归的书！这样的书不太常见。许多人认为递归是一种“神秘”的编程技术，而且一般不建议使用这种技术。奇怪的是，各种稀奇古怪的面试题之中始终出现递归。
其实学递归有很多实际的好处。递归式的思考确实是解决问题的一种手段。递归的本质就是把大问题拆解成多个小问题。在拆解的过程中，原来那个比较困难的大问题或许会演变成一种易于解决的形式。这种思维对软件设计相当有用，即使不在设计中使用递归，学会这样思考也是有益的。各种水平的程序员都应该学递归。
谈到递归，我有许许多多的话要说，刚开始写这篇序时，我想写好几个小故事，是几个发生在我朋友身上的故事，他们都学会了递归，尽管各自的递归方式不同，但最终都能得到相似的结果。首先，我想讲的是Ben的故事，他精通递归的应用，他当时在正式的产品中写下了非常复杂的Python代码。这段代码难以理解。Ben后来不知道去了哪里。
result = [(lambda r: lambda n: 1 if n < 2 else r(r)(n-1) + r(r)(n-2))(
lambda r: lambda n: 1 if n < 2 else r(r)(n-1) + r(r)(n-2)))(n)
for n in range(37)]接下来，我想讲的是 Chelsea 的故事，她学了递归之后，不管遇到什么问题都想用递归解决，所以很快就被解雇了。你可能不知道 No Starch出版社的编辑多么害怕我在序里讲这种故事。“可不敢把这些故事放在书前面，这会把读者都吓跑！”他们的担忧确实有道理。事实上，现在你看到的序的第2段文字原本打算放在这两个故事之后，我本来想先用两个故事让你大吃一惊，再说那段话，安慰你。假如我还像当初想的那样写，那你可能在看过Ben与Chelsea的故事之后，就直接被吓跑，选择读一本讲解设计模式的书了。
写序是一件严肃的事情，所以很抱歉，Ben与Chelsea的故事只好下次再讲。现在回到正题：在日常的编程工作中，大多数问题确实用不到递归。于是，这项技术就蒙上了神秘的面纱。本书应该能够揭开递归的面纱。
最后要说的是，开始学递归之前，请记住，递归要求我们用新的方式思考原来的问题。别担心，你会慢慢习惯这样的思考方式。总之，递归应该很有意思才对，或者递归是有一点儿意思的。所以，深入学习递归吧！
——戴维·贝兹利（David Beazley）
Python Cookbook与Python Distilled的作者
Sarah Kuchinsky，理学硕士，企业培训师及顾问。她用Python实现卫生系统建模、游戏开发与任务自动化等。她不仅是North Bay Python 会议的联合创始人和PyCon US的指导委员会主任，还是PyLadies Silicon Valley的主要组织者。
封面上不应该只写我一个人的名字。我要感谢出版人 Bill Pollock、编辑 Frances Saux、技术审校者 Sarah Kuchinsky、责任印制 Miles Bond、印制经理 Rachel Monaghan，以及 No Starch 出版社的其他员工，他们给了我极大的帮助。
最后，感谢家人、朋友与读者给我提供建议和支持。
递归是一种编程技术，能够产生相当优雅的代码，但它也经常会把写代码和看代码的程序员给弄糊涂。这并不是说程序员可以或者应该忽略递归。尽管大家都知道递归比较难，但是这是计算机科学领域的一个重要话题，它能让你敏锐地观察到编程问题的解法。了解递归至少能够令你在编程面试中取得好成绩。
如果你是学生，而且对计算机专业感兴趣，那么必须先攻克递归这个难点，然后才能理解其他常见的算法。如果你在毕业后参加编程培训或者通过自学而了解编程，那么可能不需要像计算机专业的人那样，必须学习一些偏理论的计算机知识，但即使如此，你也需要了解递归，因为在参加编程面试时，你仍然可能会遇到要在白板上写递归代码的情况。如果你已经是一位有经验的软件开发者，但是从来没有接触过递归算法，那么你接下来可能会发现不学递归实在太可惜了。
其实不必担心。虽然递归讲起来比较困难，但是理解起来并没有那么困难。许多人对递归有误解是因为他们没有得到很好的指导，而不是因为递归本身有多么困难。另外，递归函数在日常编程中用得不频繁，因此许多人即使不懂或不使用递归，也能写程序。
递归算法背后的理念是相当精彩的，即便你在编程中很少使用递归，这种理念也能够帮助你更深入地理解编程。另外，递归之美还体现在图形上面。这指的是一种名为分形（fractal）的数学艺术，这种形状与它自身的一部分是相似的。
然而，本书并非一味吹捧递归。本书会对这项技术的某些用法提出严厉的批评。许多问题明明有更简单的解法，但有些人偏要使用递归，这是一种滥用。递归算法理解起来可能比较困难，性能或许比较差，而且容易引发导致程序崩溃的栈溢出（stack overflow）错误。有些程序员之所以用递归，并不是因为他们觉得某个问题应该通过递归解决，而是想写出其他程序员很难看懂的代码，从而显得自己很聪明。计算机科学家约翰·维兰德（John Wilander）博士说过：“读完计算机科学专业的博士之后，他们会把你带到一间特别的房间，告诉你千万不要真的使用递归，这只是用来吓唬那些大学生的，让他们觉得编程很难。”
你可能想轻松应对编程面试，也可能想画出漂亮的数学图形，还有可能想深入理解递归，无论如何，本书都能带你进入递归的奇妙世界（如果把递归比作兔子洞，那么其中还有很多小的兔子洞，而那些小的兔子洞中又有许多更小的兔子洞）。递归是计算机领域里能让人从新手变成老手的一门技术。读过学习本书，你不仅会掌握这项优秀的技术，还能了解到许多人不清楚的一件事：递归其实没有我们想象中的那么复杂。
本书是写给那些害怕递归算法或对递归算法感兴趣的人的。对于程序员新手或计算机科学专业大一的学生而言，递归好像是魔法。许多递归课程很难懂，这让许多人非常沮丧，甚至望而生畏。对于这些读者，我希望本书直白的解读和大量的示例能让递归更容易理解。
要看懂本书，你必须会编写基本的 Python 程序或 JavaScript 程序，因为正文中的示例代码是用这两种语言编写的。本书中的代码去除了多余的部分，只保留了精华。你只要知道怎么创建并调用函数，而且明白全局变量与局部变量有什么区别，就能够看懂书中的所有示例。
本书有14章。
第1部分包含第1～9章。
第1章解释什么叫递归，并说明编程语言中函数的实现方式与函数调用方式为什么会很自然地形成递归。该章还会说明递归为什么不像想象中那样神奇。
第2章深入讨论递归与迭代的区别及相似之处。
第3章讲解经典的递归算法。
第4章讨论一种很适合用递归解决的问题，也就是树状结构的遍历问题，例如，当走迷宫或浏览目录时，有可能需要做这样的遍历。
第5章讨论如何用递归把大问题拆分成多个小问题，并讲解常见的分治算法。
第6章讨论涉及排列与组合的递归算法，以及适合用这些算法解决的常见编程问题。
第7章讲解在用递归解决实际问题时提高编码效率的一些简单的技巧——记忆化与动态规划。
第8章讲解尾调用优化及其原理。
第9章展示一些可以用递归算法绘制的图形。在该章中，我们使用turtle模块生成这些图形。
第2部分包含第10～14章。
第10章介绍如何实现文件查找器项目，用于根据用户提供的搜索参数搜索计算机中的文件。
第11章讨论如何实现迷宫生成器项目——用递归回溯算法自动生成任意大小的迷宫。
第12章讲述如何实现滑块拼图项目，用于解决滑块拼图（这种拼图通常由 15 个可以横竖滑动的方块构成）问题。
第13章讨论如何实现分形图案制作器项目，生成指定的分形图案。
第14章讨论如何实现画中画制作器项目：用 Pillow 这个图像操纵模块，生成递归式的画中画效果。
仅仅把本书读一遍是不可能知道怎样用代码实现递归的。本书包含许多用 Python 与 JavaScript 语言编写的示例代码，以方便你练习编程。如果你是编程新手，建议了解一般的编程知识以及Python编程语言。
建议你用调试器（debugger）把本书的程序逐行执行一遍。调试器允许每次只执行程序中的一行代码，让你查看程序状态在执行过程中的变化情况。
本书大多数章会同时展示 Python 代码与 JavaScript 代码。Python 代码保存在.py 文件中，JavaScript代码保存在.html文件（而不是.js文件）中。例如，下面是一段Python代码，它保存在hello.py文件中。
print('Hello, world!')下面是对应的JavaScript代码，它保存在hello.html文件中。
<script type="text/javascript">
document.write("Hello, world!<br />");
</script>这两段代码是编写 Python程序及JavaScript程序的基础，它们展示了如何用两种不同的编程语言，实现相同的效果。
提示：
hello.html 文件里的 <br /> 标记用于换行，如果不换行，所有的内容就会输出到同一行中。Python的print()函数会在文本末尾自动换行，而JavaScript的document.write() 函数不会，所以需要手动添加<br />标记。
建议你动手输入这些程序代码，而不是直接把源代码复制并粘贴到源文件里。自己输入代码能够促进你深入理解其中的每行内容，从而像骑自行车一样形成肌肉记忆。
上面那种 .html文件的写法严格来说并不是完全正确的，因为其中缺少几个必备的HTML标记，例如<html>与<body>等，但是浏览器可以识别此类文件并解读其内容。笔者故意没把那几个标记写上去，这样可以让书中的代码简洁易读。因为这毕竟不是一本专门讨论 Web 开发的书，所以没必要严格遵守编写.html文件时的一些原则。
每台计算机应该都有网页浏览器，所以书中那些包含JavaScript代码的.html文件应该都是能够查看的。但要运行Python代码，你必须单独安装 Python 开发环境。你可以从Python官网下载适用于Windows系统、macOS以及Linux系统的Python。注意，一定要下载Python 3（如3.10），而不要下载 Python 2，因为 Python 3 做了一些与 Python 2 不兼容的改动，本书里的程序是按照 Python 3 的标准编写的，这些程序无法正确地在Python 2环境中运行，有些程序甚至根本就无法执行。
你可以使用安装 Python 时附带的 IDLE 编辑器来写 Python 代码，也可以另外安装一款免费的编辑器，如 Mu、PyCharm社区版或Visual Studio Code。
在 Windows 系统中，单击屏幕左下角的 Start（开始）菜单，然后在搜索框中输入 IDLE，最后选择搜索结果之中的 IDLE (Python 3.10 64-bit)，就能启动 IDLE。
在 macOS 中，打开 Finder 窗口并选择 Applications → Python 3.10，然后单击 IDLE 图标，就能启动 IDLE。
在Linux系统中，首先选择Applications → Accessories → Terminal，然后输入并执行idle3命令，就能启动IDLE。你也可以单击屏幕顶端的Applications，并选择 Programming，然后单击idle 3。
IDLE 有两种窗口。一种是带>>> 提示符的交互式 shell 窗口，这种窗口每次可以执行一条指令。如果你只需要运行少量 Python 代码，那么这种窗口比较有用。另一种是文件编辑器窗口，可以在其中输入完整的 Python 程序并将其存为.py文件。本书中的 Python 源代码适合用这种窗口来运行。选择IDLE中的File → New File 选项，会出现一个新的文件编辑器窗口。选择IDLE中的 Run → Run Module选项，就可以运行该窗口中的代码。另外，你也可以直接按F5键来运行代码。
计算机里的网页浏览器可以运行JavaScript程序，并显示其所输出的内容。然而，为了编写JavaScript代码，你还需要使用文本编辑器。你可以选择Notepad（记事本）或TextMate这种简单的编辑器，也可以安装专门用来写代码的编辑器，如IDLE或Sublime Text。
把JavaScript程序的代码输入好之后，将其另存为.html文件。在浏览器中打开这样的文件并观察运行结果。任何新的网页浏览器都能运行.html文件中的JavaScript代码。
要获得本书的源代码，请在异步社区本书页面中单击“配套资源”，跳转到下载界面，按提示进行操作即可。注意，为保证购书读者的权益，该操作会给出相关提示，要求输入本书第87页的配套资源验证码。
如果您是教师，希望获得教学配套资源，请在社区本书页面中直接联系本书的责任编辑。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区（https://www.epubit.com），按书名搜索，进入本书页面，单击“发表勘误”，输入相关信息，单击“提交勘误”按钮即可（见下图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们。
如果您所在的学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”（www.epubit.com）是由人民邮电出版社创办的IT专业图书社区，于2015年8月上线运营，致力于优质内容的出版和分享，为读者提供高品质的学习内容，为作译者提供专业的出版服务，实现作者与读者在线交流互动，以及传统出版与数字出版的融合发展。
“异步图书”是异步社区策划出版的精品IT图书的品牌，依托于人民邮电出版社在计算机图书领域几十年的发展与积淀。异步图书面向IT行业以及各行业使用IT的用户。
本部分内容
■ 第1章 递归
■ 第2章 递归与迭代
■ 第3章 经典的递归算法
■ 第4章 回溯与树的遍历算法
■ 第5章 分治算法
■ 第6章 排列与组合
■ 第7章 记忆化与动态规划
■ 第8章 尾调用优化
■ 第9章 绘制分形
递归听起来令人望而生畏。许多人觉得递归比较难懂，但实际上它只依赖两个东西，一个是函数调用，另一个是栈（stack，这是一种数据结构）。
大多数程序员按照执行顺序追踪程序行为。以这种方式阅读代码比较容易，你只需要先指着程序的第 1 行代码，把这行代码看完，然后指向第 2 行，把那行代码也看完，接下来依次向下即可。有时，你可能要跳到原来已经看过的某一行代码上面，或者进入某个函数之中，把那个函数的代码看完之后，再返回当初进入该函数的地方。无论程序怎么执行，我们都可以像这样，把程序所做的事情以及它做事的步骤弄明白。
然而，要想理解递归，你还必须熟悉一种不太显眼的数据结构——调用栈（call stack），这种栈用来控制程序的执行流程（flow of execution）。大多数编程新手不太了解栈，因为编程教材在讨论函数调用时，通常并不会提起这个概念。另外，这种自动管理函数调用的调用栈，并未出现在源代码之中，因此许多初学者没有意识到它。
如果你根本就看不见它，而且也不知道有这样一个东西存在，那么自然很难理解它究竟是怎么回事。本章要做的就是开门见山地告诉大家，递归并不是一个特别复杂的概念，它其实相当优雅。
开始定义递归之前，先讲几个与递归有关的笑话，讲完之后，我们就进入正题。第1个笑话是“要理解什么是递归，你必须先理解什么是递归才行”。
根据笔者这几个月写书的经历，我保证，以后你会觉得这个笑话越想越有意思。
第 2 个笑话如下：如果你在搜索引擎中搜索 recursion（递归），那么显示搜索结果的页面里可能会出现“Did you mean: recursion”字样，问你是不是要查 recursion，当你单击这个词所在的链接之后，又会继续在搜索引擎之中搜索 recursion 一词，并再次看到图 1-1 所示的页面。
图1-2展示了第 3 个笑话，这张图选自 xkcd 网络漫画。
科幻电影——Inception（《盗梦空间》）中的许多情节是递归的。电影中的人物在一个梦里做另一个梦，又在那个梦里继续做梦。
最后，学计算机的人怎能忘了拿希腊神话里的半人马（centaur）开个玩笑呢？图1-3所示为递归版的半人马（recursive centaur），它的下半部分是马，上半部分是由下半部分递归而成的。
图1-1 在搜索引擎中搜索 recursion
图1-2 I’ᴍ Sᴏ Mᴇᴛᴀ, Eᴠᴇɴ Tʜɪꜱ Aᴄʀᴏɴʏᴍ [IS META]（就连这句话的首字母缩略语
也是IS Mᴇᴛᴀ）（图片来源：Randall Munroe）
图1-3 递归版的半人马（图片来源：Joseph Parker）
看了这些笑话，你可能觉得递归是一种元概念，是一种引用自身的东西，是一种梦中梦或镜中镜之类的东西。其实我们应该给递归的（recursive）这个形容词下一个明确的定义：某事物是递归的意味着需要用该事物本身来定义它自己。也就是说，这样的东西会在它的定义里引用它自己。
图1-4（a）～（c）展示了谢尔宾斯基三角形，这种三角形是等边三角形，其内部包含一个倒置的小等边三角形，这个倒置的小等边三角形让大的等边三角形里出现了另外 3 个小的等边三角形，而那 3 个小的等边三角形本身也是谢尔宾斯基三角形。从这个定义可以看出，谢尔宾斯基三角形用其自身定义它自己。
图1-4 谢尔宾斯基三角形
编程语境中的递归主要用来形容函数。递归函数（recursive function）就是那种调用其自身的函数。开始研究递归函数之前，我们先退一步，看看普通的函数是怎么运作的。许多程序员认为函数调用是本来就应该有的东西，但是看了1.2节之后，即使相当有经验的程序员也会觉得函数确实有必要重新审视。
函数可以描述为程序中的小型程序。几乎每一种编程语言都支持函数。如果你想在程序的 3 个地方分别运行某组指令，那么可以把这组指令写成一个函数，然后在这 3 个地方分别调用该函数，这样你就不用将这套指令复制并粘贴 3 份。函数能够精简程序的代码，使这些代码更加清晰。另外，这样写出来的程序也比较容易修改。如果你要修复 bug 或添加新的功能，那么只需修改一个地方（也就是那个函数）即可，而不用把 3 个地方全改一遍。
所有的编程语言都为函数提供如下 4 个特性。
❏ 函数可以拥有一套代码，程序在调用该函数时，会执行这套代码。
❏ 程序调用函数时，可以给它传递参数（argument，其实就是一些值）。这些参数是这次调用该函数时的输入（input）数据。函数可以拥有零个或多个参数。
❏ 函数可以带有返回值。这是这次调用该函数时的输出（output）数据。有些编程语言允许函数不返回任何值，或者允许其返回空值（null value），如undefined或None 这样的值。
❏ 程序能够记住它这次是在执行到哪一行代码时调用这个函数的，等到程序调用完函数之后，它会返回那行代码所在的位置，继续往下执行。
虽然有些编程语言之中的函数可能还支持其他特性，或者允许程序用另外一些方式调用函数，但是以上 4 个特性是每一种编程语言中的函数都应该支持的。在编写源代码的过程中，我们应该能够直观地体会到前 3 个特性，但第 4 个特性值得思考。也就是说，我们要问一问：当函数返回时，程序是怎么知道这次应该返回什么地方的？
为了更好地理解这个问题，编写 functionCalls.py 程序，并在其中定义 3 个函数，也就是 a()、b()与 c()，程序本身会调用 a()，a()会调用 b()，b()又会调用 c()。
Python
def a():
print('a() was called.')
b()
print('a() is returning.')
def b():
print('b() was called.')
c()
print('b() is returning.')
def c():
print('c() was called.')
print('c() is returning.')
a()与这段代码等效的 JavaScript 代码写在 functionCalls.html 程序中。
JavaScript
<script type="text/javascript">
function a() {
document.write("a() was called.<br />");
b();
document.write("a() is returning.<br />");
}
function b() {
document.write("b() was called.<br />");
c();
document.write("b() is returning.<br />");
}
function c() {
document.write("c() was called.<br />");
document.write("c() is returning.<br />");
}
a();
</script>运行这个程序，会看到下面这样的输出结果。
a() was called.
b() was called.
c() was called.
c() is returning.
b() is returning.
a() is returning.由输出的内容可见，程序依次启动了 a()、b()、c() 这 3 个函数。然而，返回顺序与启动顺序相反，程序先从 c()中返回，然后从 b()中返回，最后从 a()中返回。注意观察程序输出的这些文字有何规律。程序调用完 c()函数之后，返回 b()函数中，然后显示 b()is returning.。显示完这句，意味着程序调用完了 b()函数，于是它返回 a()函数中，然后显示 a()is returning.。显示完这句，意味着程序调用完了 a()函数，而调用 a()函数所用的那行代码（也就是 Python 版的 a()与 JavaScript 版的 a();）是主程序的最后一行代码，所以执行完这行之后，整个程序就结束了。由于程序可以在执行过程中调用函数，因此它并不一定是按照源文件中的代码顺序单纯从上往下执行的，而有可能在各函数之间辗转。
问题在于，程序是如何知道 c()到底是由 a()函数还是由 b()函数调用的呢？这种细节需要由调用栈来处理。为了搞清楚调用栈是怎么知道执行完函数之后，应该返回什么地方的，我们首先必须理解栈这个概念。
前面讲过几个笑话，其中一个是“要理解什么是递归，你必须先理解什么是递归才行”。其实这句话不对，要想把递归真正弄懂，你首先必须理解的应该是栈。
栈是计算机科学中一种极其简单的数据结构。它能够像列表那样，存储多个值，但与列表不同，你只能从栈的顶部（top）添加或移除元素。如果你是用列表（list）或数组（array）来实现栈的，这个顶部指的就是该列表或该数组的最后一个元素所在的位置。如果该列表或数组是按照从左到右的方向增长的，栈顶就位于此列表或此数组的最右端。往栈中添加元素称为将值压入栈中（即入栈），从栈中移除元素称为将值从栈中弹出（即出栈）。
举一个示例，假设你与某人之间有一段漫长的对话。一开始，你在说你的朋友 Alice，说着说着，你想起来同事 Bob 的事情，但为了解释这个事情，你又得提到亲戚 Carol。说完 Carol 之后，你继续说 Bob 的事情，说完 Bob 的事情，你又继续说 Alice 的事情。然而，还没说完，你又想起了你的兄弟 David，于是又开始讲 David。讲完David的事情之后，你才总算把一开始要说的那个 Alice 的故事彻底说完。
这样的对话在结构上与栈很像，如图 1-5 所示。说它像，是因为当前讨论的话题始终位于结构的顶部，也就是位于栈顶。
图 1-5 用栈来表示漫长的对话
在这个对话栈中，新提到的话题会添加到栈顶，而且会在讨论完之后，从栈顶移走。前面提到还没有讨论完的那些话题会压在当前讨论的话题下面，这就是栈这种结构“记忆”数据的方式。
在Python语言中，用列表实现栈，但是我们必须约束自己只能通过列表的 append()和pop()方法执行入栈与出栈操作，以修改栈的内容。JavaScript语言可以通过数组实现栈，并分别使用push()和pop()方法执行入栈与出栈操作。
提示
Python 用的术语是列表（list）与项（item），在JavaScript中，与之对应的则是数组（array）与元素（element），对于这里要讲的内容来说，这两组称呼实际上均是一个意思。笔者采用列表与项称呼这两种语言中的此类容器以及其中的每一个单元[1]。
[1] 在不引发歧义的前提下，译文酌情灵活换用各种说法。——译者注
下面举一个示例，我们写一个名为 cardStack.py 的程序，让它用字符串表示相应的牌，并将其压入名为cardStack的栈（这个栈是用列表实现的）中，再从栈顶弹出一张牌。
Python
cardStack = ❶ []
❷ cardStack.append('5 of diamonds')
print(','.join(cardStack))
cardStack.append('3 of clubs')
print(','.join(cardStack))
cardStack.append('ace of hearts')
print(','.join(cardStack))
❸ cardStack.pop()
print(','.join(cardStack))等效的JavaScript代码写在 cardStack.html程序中。
JavaScript
<script type="text/javascript">
let cardStack = ❶ [];
❷ cardStack.push("5 of diamonds");
document.write(cardStack + "<br />");
cardStack.push("3 of clubs");
document.write(cardStack + "<br />");
cardStack.push("ace of hearts");
document.write(cardStack + "<br />");
❸ cardStack.pop()
document.write(cardStack + "<br />");
</script>运行这段代码，会看到下面的输出信息。
5 of diamonds
5 of diamonds,3 of clubs
5 of diamonds,3 of clubs,ace of hearts
5 of diamonds,3 of clubs栈一开始是空的（❶）。然后，程序把 3 个字符串依次压入栈中（❷），以表示 3 张牌。接下来，程序从栈中弹出一张牌，也就是把栈顶的红桃 A 拿走（❸），这样原来压在它下面的梅花 3 就会重新出现在栈顶。图 1-6 按照从左到右的顺序演示了在程序执行的过程中cardStack 的状态是如何变化的。
你只能看到栈顶的那张牌，从程序的角度来讲，这意味着你只能看到栈顶的那个值。在这种最简单的实现方式之中，我们无法得知栈里总共有多少张牌（或者说，我们不知道栈里总共有多少个值）。我们只能知道这个栈是不是空的。
图 1-6 栈起初是空的，然后程序向栈中压入 3 张牌，最后又从栈中弹出一张牌
栈是一种 LIFO 型数据结构，LIFO 的全称是 Last In, First Out（后进先出），因为最后压入栈中的值始终首先从栈中弹出。这有点像网页浏览器的 Back（后退）按钮。浏览器的历史记录就好比一个栈，它会把你访问过的每张网页按顺序记录下来。浏览器始终显示在历史记录之中位于“栈顶”的那张网页。如果单击网页中的某个链接，那么浏览器会把该链接所指向的新网页压入栈中；如果单击后退按钮，那么浏览器会把当前的网页从历史记录之中弹出，并开始显示压在它下面的那张网页。
除刚才举的漫长对话与浏览器历史记录的例子之外，计算机程序也在使用栈。程序的调用栈可以直接简称为栈，这种栈由帧对象（frame object）构成，这些帧对象简称帧（frame）。在每一帧中，都有与某次函数调用有关的信息，例如，程序在执行到哪一行代码时调用该函数。有了这些信息，程序从函数中返回之后，就可以从之前调用该函数的那个地方继续往下执行。
帧对象是在程序调用函数时创建并压入调用栈之中的。当程序从函数中返回时，相应的帧对象也会从栈中弹出。如果程序调用某个函数，该函数又调用另一个函数，而那个函数又继续调用别的函数，那么栈中会出现 3 个帧对象。等程序执行完这些函数并返回之后，调用栈会变空（或者说，调用栈中的帧对象个数会降为 0）。
程序员不需要专门写代码来处理这种帧对象，因为这种帧对象是由编程语言自动处理的。不同的编程语言会用不同的方式处理帧对象，但总的来说，帧中都会有下列内容。
❏ 返回地址（return address），或者程序从函数中返回之后，应该从哪一个地方继续往下执行。
❏ 这次调用该函数时，程序向函数传递的参数。
❏ 在函数调用过程中创建的一组局部变量。
例如，查看localVariables.py 程序，这个程序与之前的functionCalls.py与functionCalls.html程序一样，也定义了 3 个函数。
Python
def a():
❶ spam = 'Ant'
❷ print('spam is ' + spam)
❸ b()
print('spam is ' + spam)
def b():
❹ spam = 'Bobcat'
print('spam is ' + spam)
❺ c()
print('spam is ' + spam)
def c():
❻ spam = 'Coyote'
print('spam is ' + spam)
❼ a()等效的 JavaScript 程序写在 localVariables.html 文件中。
JavaScript
<script type="text/javascript">
function a() {
❶ let spam = "Ant";
❷ document.write("spam is " + spam + "<br />");
❸ b();
document.write("spam is " + spam + "<br />");
}
function b() {
❹ let spam = "Bobcat";
document.write("spam is " + spam + "<br />");
❺ c();
document.write("spam is " + spam + "<br />");
}
function c() {
❻ let spam = "Coyote";
document.write("spam is " + spam + "<br />");
}
❼ a();
</script>运行这段代码，会看到这样的输出结果。
spam is Ant
spam is Bobcat
spam is Coyote
spam is Bobcat
spam is Ant程序调用 a()函数时（❼），会创建一个帧对象并将其放在调用栈的顶部。在这一帧中，不仅保存着程序传给函数 a()的各种参数（在本例中，函数 a()不需要参数，因此程序没有给它传递参数），还保存着这次调用函数 a()时创建的局部变量 spam（❶），以及程序在执行完该函数之后应该回到的位置。
在调用a()函数时，会显示出局部变量 spam 的值，也就是 Ant（❷）。然后，它会调用 b()函数，这时程序会新建一个帧对象，并将其放置在调用栈的顶部，于是这一帧就出现在刚才为调用 a()函数而创建的那一帧之上。在调用b()函数时，会创建它自己的局部变量 spam（❹），然后调用 c()函数（❺）。这时，程序又会为这次的调用操作创建一个新的帧对象，并将其放置在调用栈顶部，在这个帧对象中，记录 c()函数中的那个局部变量 spam（❻）。程序从某个函数返回时，会把相应的帧对象从调用栈中弹出来。由于帧对象之中记录着与返回位置有关的信息，因此程序知道自己接下来应该从哪里继续执行。等到程序把这 3 个函数全调用完之后（或者说，等到程序依次从这 3 个函数返回之后），调用栈就变空了。
图 1-7 演示了程序调用各函数并从这些函数中返回的过程中调用栈的状态是如何变化的。注意，这 3 个函数中的 3 个局部变量全叫作 spam，这是为了强调，即使某函数中的某个局部变量与其他函数中的局部变量重名，也不会引起冲突，因为这些变量各自独立，它们可以拥有不同的值。
图 1-7 调用栈的状态在 localVariables .html程序的执行过程中如何变化
由此可见，编程语言是允许各函数之间的局部变量重名的，本例中局部变量都叫 spam。这是因为这些变量分别保存在不同的帧对象中。当程序提到源代码中的某个局部变量时，它所指的其实是当前位于调用栈顶部的帧对象中保存的变量。
每个运行着的程序都有它的调用栈，如果这是个多线程的程序，那么其中每个线程会分别拥有各自的调用栈。然而，这并未反映在程序的源代码中，你从代码中是看不出调用栈的。不像其他数据结构那样，调用栈需要保存在变量之中，它由系统在后台自动处理。
调用栈没有出现在源代码中，这正是初学者很难理解递归的主要原因。要理解递归，必须理解调用栈，而程序员无法直接在代码中看到这种机制。我们已经把栈这种数据结构与调用栈的工作原理讲完了，所以接下来理解递归应该就容易多了。单独来看，函数与栈都是相当简单的概念，将这两个概念结合起来可以帮助我们理解递归究竟是怎么一回事。
递归函数（recursive function）就是调用其自身的函数。下面这个 shortest.py 程序是 Python 中篇幅最短的递归函数。
Python
def shortest():
shortest()
shortest()等效的 JavaScript 代码写在 shortest.html 文件中。
JavaScript
<script type="text/javascript">
function shortest() {
shortest();
}
shortest();
</script>shortest() 函数不做其他事情，它唯一要做的就是调用自身。而这又会让程序继续调用 shortest() 函数，这次调用又会触发下一次调用，于是程序好像会一直这样调用下去。这与那个神奇的说法有点类似，地球下面有一只巨大的乌龟，那只乌龟下面又有另一只乌龟，在那只乌龟下面还有其他的乌龟……
这种“一只乌龟出现在另一只乌龟背上”的理论并不能很好地解释整个宇宙，而且同样无助于我们理解递归函数。调用栈需要占据计算机的内存，而计算机的内存是有限的，因此程序不可能像真正的无限循环那样，一直运行下去。这种程序到最后肯定会崩溃，并显示出一条错误消息。
提示
为了观察 JavaScript 程序的错误消息，你必须打开浏览器的开发者工具，大多数浏览器的开发者工具界面可以通过按键盘上的 F12 键显示。然后，你需要选择其中的 Console 选项卡，以观察错误消息。
Python 版的 shortest.py 程序会给出下面的错误消息。
Traceback (most recent call last):
File "shortest.py", line 4, in <module>
shortest()
File "shortest.py", line 2, in shortest
shortest()
File "shortest.py", line 2, in shortest
shortest()
File "shortest.py", line 2, in shortest
shortest()
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded用 Google Chrome 浏览器运行 JavaScript 版的 shortest.html 程序，会看到下面这样的错误消息（用其他浏览器运行，也会看到类似的错误消息）。
Uncaught RangeError: Maximum call stack size exceeded
at shortest (shortest.html:2)
at shortest (shortest.html:3)
at shortest (shortest.html:3)
at shortest (shortest.html:3)
at shortest (shortest.html:3)
at shortest (shortest.html:3)
at shortest (shortest.html:3)
at shortest (shortest.html:3)
at shortest (shortest.html:3)
at shortest (shortest.html:3)这种 bug就是栈溢出（stack overflow）。那个相当流行的技术问答网站——Stack Overflow正得名于此。如果程序始终像这样一直调用函数，而这些函数又一直都没有返回，调用栈就会持续增长，直至耗尽计算机的全部内存。为了防止出现这种现象，Python 与 JavaScript 解释器如果发现程序经过一定数量的函数调用操作之后，依然没有返回，那么会令该程序崩溃。
这个限度称为最大递归深度（maximum recursion depth）或最大调用栈尺寸（maximum call stack size）。对于 Python 语言来说，这指的是 1000 次函数调用。对于 JavaScript 语言来说，调用栈能够达到的最大深度与运行代码所用的浏览器有关，一般来讲，至少是 10000 次。栈溢出可以理解为调用栈堆得太高了（也可以说调用栈消耗的计算机内存量太大了），如图 1-8 所示。
图 1-8 调用栈堆得太高就会造成栈溢出
栈溢出并不会令计算机受损。计算机如果发现程序调用函数的次数超限，并且一直没有返回，它就会令程序终止。最坏的后果就是该程序之中尚未保存的工作会丢失。要防止程序发生栈溢出错误，你需要知道什么叫作基本情况，这会在1.6节讲解。
刚才那个发生栈溢出错误的程序会调用 shortest() 函数，而这个函数只会反复调用自身，永远不会返回。为了不让程序崩溃，我们必须设定一种情况或者一组条件，让函数在满足这种情况时能够返回，而不再继续调用自身。这样的情况就称为基本情况（base case）。与之相对，那种让函数继续调用其自身的情况则称为递归情况（recursive case）。
所有的递归函数都需要有至少一种基本情况与至少一种递归情况。如果没有基本情况，函数就会一直递归调用下去，从而导致栈溢出。如果没有递归情况，函数就不会调用其自身，从而变成一个普通函数，因此无法成为递归函数。在开始编写递归函数时，最好能先确定基本情况与递归情况。
请看下面这个 shortestWithBaseCase.py 程序，该程序重新设计了刚才的 shortest() 函数，把它定义成一个不会引发栈溢出的递归函数。
Python
def shortestWithBaseCase(makeRecursiveCall):
print('shortestWithBaseCase(%s) called.' % makeRecursiveCall)
if not makeRecursiveCall:
# 基本情况
print('Returning from base case.')
❶ return
else:
# 递归情况
❷ shortestWithBaseCase(False)
print('Returning from recursive case.')
return
print('Calling shortestWithBaseCase(False):')
❸ shortestWithBaseCase(False)
print()
print('Calling shortestWithBaseCase(True):')
❹ shortestWithBaseCase(True)等效的JavaScript 代码写在 shortestWithBaseCase.html 文件之中。
JavaScript
<script type="text/javascript">
function shortestWithBaseCase(makeRecursiveCall) {
document.write("shortestWithBaseCase(" + makeRecursiveCall +
") called.<br />");
if (makeRecursiveCall === false) {
// 基本情况
document.write("Returning from base case.<br />");
❶ return;
} else {
// 递归情况
❷ shortestWithBaseCase(false);
document.write("Returning from recursive case.<br />");
return;
}
}
document.write("Calling shortestWithBaseCase(false):<br />");
❸ shortestWithBaseCase(false);
document.write("<br />");
document.write("Calling shortestWithBaseCase(true):<br />");
❹ shortestWithBaseCase(true);
</script>运行这段代码，应该会看到这样的结果。
Calling shortestWithBaseCase(False):
shortestWithBaseCase(False) called.
Returning from base case.
Calling shortestWithBaseCase(True):
shortestWithBaseCase(True) called.
shortestWithBaseCase(False) called.
Returning from base case.
Returning from recursive case.这个函数并不打算执行有意义的操作，它只用来简要地展示怎样编写递归函数（假如把那些用来输出文字的语句去掉，那么函数的代码还能变得更少，但这里需要这些文字，以解释函数的运行情况）。当用 False 作为参数调用这个函数时（也就是主程序执行 shortestWithBaseCase(False) 时，❸），函数遇到的是基本情况，因此会直接返回（❶）。然而，接下来，主程序又以 True 作为参数调用这个函数（也就是 shortestWithBaseCase(True)，❹），这次函数遇到的是递归情况，在这种情况下，它会以 False 作为参数继续调用自身（也就是执行 shortestWithBaseCase (False)，❷）。
注意一个重要的现象：函数在以 False 为参数递归调用完自身之后（也就是执行完 shortestWithBaseCase(False) 之后，❷），并不会直接返回程序最初调用此函数的那个地方（❹），而会继续执行上一次遇到递归情况之后还未执行完的那些代码，因此程序会输出Returning from recursive case.字样。函数从基本情况中返回，并不意味着早前还没有执行完的那些递归调用也会立即结束。你必须记住这一点，才能理解 1.7 节要讲的 countDownAndUp() 。
函数在递归情况下所要执行的代码可以分成两部分：一部分是进入下一轮递归之前所要执行的代码；另一部分是执行完下一轮递归之后所要执行的代码。有些函数在递归情况下需要执行两次递归调用，例如，第 2 章会讲到计算斐波那契数列（Fibonacci sequence）第 N 项的函数，那个函数在递归情况下就需要执行两次递归：一次是递归计算第 N−1 项，另一次是递归计算第 N−2 项。那个函数在递归情况下所要执行的代码则需要分成三部分：第一部分是进入下一轮的第一次递归之前所要执行的代码；第二部分是执行完下一轮的第一次递归且尚未进入第二次递归时所要执行的代码；第三部分是执行完下一轮的第二次递归之后所要执行的代码。这里我们还用比较简单的递归函数来举例。
这样划分是想强调，函数遇到了基本情况并不一定意味着处理完这种情况之后，整个递归算法就结束。这只意味着函数不会继续递归调用。
下面举一个示例，这个 countDownAndUp.py 程序定义了一个递归函数，该函数能够从某个正整数开始倒数，直至数到 0，然后正着数，直至数到原来那个数本身。
Python
def countDownAndUp(number):
❶ print(number)
if number == 0:
# 基本情况
❷ print('Reached the base case.')
return
else:
# 递归情况
❸ countDownAndUp(number - 1)
❹ print(number, 'returning')
return
❺ countDownAndUp(3)等效的 JavaScript 代码写在 countDownAndUp.html 文件中。
JavaScript
<script type="text/javascript">
function countDownAndUp(number) {
❶ document.write(number + "<br />");
if (number === 0) {
// 基本情况
❷ document.write("Reached the base case.<br />");
return;
} else {
// 递归情况
❸ countDownAndUp(number - 1);
❹ document.write(number + " returning<br />");
return;
}
}
❺ countDownAndUp(3);
</script>运行这段代码，会看到这样的输出结果。
3
2
1
0
Reached the base case.
1 returning
2 returning
3 returning要记住，程序每次调用函数时，都会新建一帧，并将此帧压入调用栈。这一帧中，保存着这次调用该函数时所使用的参数（本例中的 number就是一个参数），以及这次调用时所建立的局部变量。因此，调用栈的每一帧中，都有各自的 number 变量。这又是解读递归式代码时一个容易弄错的地方：尽管源代码中只有一个 number 变量，但由于这是个局部变量[2]，因此每次调用 countDownAndUp() 函数时，都会产生与这次调用相对应的 number 变量，这些变量彼此是不同的。
[2] 参数也可以视为局部变量。——译者注
程序执行 countDownAndUp(3) 时（❺），会创建一帧，这一帧中 number 局部变量的值是 3。函数会把 number 变量的值输出到屏幕上（❶）。只要 number 不是 0，countDownAndUp() 函数就会以 number -1 为参数，递归调用自己（❸）。在这次递归中，程序执行的是 countDownAndUp(2)，为此，程序会新建一帧，并将其压入栈中，这一帧中的 number 局部变量的值是 2。接下来，函数遇到的还是递归情况，因此会以 1 作为参数，递归调用自身（也就是说，程序会执行 countDownAndUp(1)）。在这次递归中，函数遇到的仍是递归情况，于是又会以 0 作为参数，递归调用自身（也就是说，程序会执行countDownAndUp(0)）。
程序能够实现倒着数与正着数的效果，因为它首先连续执行递归调用，然后又逐层从这些调用之中返回。当程序执行到 countDownAndUp(0) 时，会遇到基本情况（❷），因而不会再递归调用自身。可是整个程序并未就此结束。当遇到基本情况时，number 局部变量的值是 0。然后，程序会从这种情况之中返回，并将栈顶的那一帧从栈中弹出，于是，刚才压在它下面的那一帧现在就重新出现在栈顶了，该帧之中的 number 局部变量仍然是 1。程序会使用调用栈中的这一帧，从它刚才递归调用 countDownAndUp(0) 的地方开始，继续往下执行（❹）。这就会把 number 变量当前的值再次输出，并在后面补上“returning”字样，从而实现到达 0 之后又正着数的效果。图 1-9 演示了程序在递归执行 countDownAndUp() 并逐层返回的过程中调用栈的状态是如何变化的。
图 1-9 调用栈会用不同的帧分别保存程序每次调用 countDownAndUp() 函数时number 局部变量的值
程序遇到基本情况之后，并不会立刻终止，第2章要讲解如何计算阶乘，你必须记住这一点，才能理解相关算法。总之，遇到基本情况之后，程序还要从它刚才进入此情况的那个地方开始，继续把之前的递归情况执行完。
这时你可能在想，用递归来写这个 countDownAndUp() 函数会让代码变得过于复杂。为什么不用迭代式的写法输出这些数字呢？迭代式的写法会用一个循环反复执行某项任务（本例中的输出数字），直至整套任务执行完毕，这种写法通常与递归式的写法相对应。
如果你觉得某个问题用循环来解决可能更简单，你基本上就应该弃用递归，转而以循环来实现。无论是初学者还是有经验的程序员，递归用起来可能都比较麻烦，而且递归式的代码也不一定始终比迭代式的代码更好或更优雅。写出易读且好懂的代码要比追求优雅的递归式代码更重要。然而，在某些场合，我们要实现的算法会很自然地把我们引向递归式的方案。涉及树状数据结构并要求回溯的算法尤其适合用递归来实现。我们会在第 2 章与第 4 章中研究这样的写法。
递归很容易让编程新手迷惑，其实它建立在一个相当简单的概念（函数可以调用其自身）之上。程序每次调用函数时，都会新建一个与这次的函数调用操作相对应的帧对象（简称帧），并将其添加到调用栈之中（这一帧中有相关的信息，例如，这次调用时建立的局部变量，以及程序调用完之后应该返回哪个地址继续执行等）。调用栈是一种栈型的数据结构，使用者只能从栈的“顶部”（也就是栈顶）添加或移除数据。这两种行为分别称为将数据压入栈中（入栈），以及从栈中弹出数据（出栈）。
调用栈由程序自行管理，因此代码中不会明确出现用来表示调用栈的变量。调用函数会促使程序将相应的帧压入调用栈，从函数中返回会促使程序将相应的帧从调用栈中弹出。
递归函数需要有递归情况与基本情况。递归情况是指会让该函数递归调用其自身的情况，基本情况是指会让函数返回并不再调用自身的情况。如果递归函数没有基本情况，或者代码有 bug 导致程序一直无法遇到基本情况，就会出现栈溢出（stack overflow）错误，进而令程序崩溃。
递归是很有用的技巧，但递归式的写法未必始终会让代码变得更好或更加优雅。这个道理会在第2章详细讲解。
除本章讲的这些内容之外，其他一些资料也介绍了递归。例如，笔者在 2018 年的North Bay Python会议上面做过一段讲解，参见“Recursion for Beginners: A Beginner’s Guide to Recursion”。V. Anton Spraul 在他的Think Like a Programmer（No Starch出版社）一书中提到了递归。另外，维基百科的Recursion词条写得很详细。
你可以安装 Python 模块——ShowCallStack。这个模块提供了 showcallstack() 函数，你可以在代码中的任何地方调用该函数，以显示程序在执行到这一点时调用栈所处的状态。这个模块的下载及安装方式参见PyPI网站。
1. 一般意义上的递归指的是什么？
2. 编程中的递归函数是什么样的函数？
3. 函数具备哪 4 个特性？
4. 什么是栈？
5. 把数据添加到栈顶和从栈顶移除数据分别与哪个术语相对应？
6. 假设首先把字母 J 压入栈中，然后压入字母 Q，再弹出栈顶的字母，接着压入字母 K，最后再度从栈顶弹出一个字母。现在这个栈是什么样子的？
7. 程序向调用栈中压入并从中弹出的东西叫什么？
8. 栈溢出是由什么问题引发的？
9. 什么叫作递归函数的基本情况？
10. 什么叫作递归函数的递归情况？
11. 正常的递归函数需要具备几种基本情况与几种递归情况？
12. 如果递归函数没有（或无法遇到）基本情况，会出现什么问题？
13. 如果递归函数没有（或无法遇到）递归情况，会出现什么问题？
