6.5　递归

视频讲解

6.5.1　递归是什么

本节小甲鱼将通过生动的讲解，告诉大家什么是递归。如果说优秀的程序员是伯乐，那么把递归比喻成“神马”是再形象不过的了。

递归到底是什么东西呢？有那么厉害吗？为什么大家常说“普通程序员用迭代，天才程序员用递归”呢？没错，通过本节的学习，你将了解递归，通过独立完成小甲鱼精心配套的课后作业，将彻底摆脱递归给你生活带来的困扰。

递归这个概念，是算法的范畴，本来不属于Python语言的语法内容，但小甲鱼基本在每个编程语言系列教学里都要讲递归，那是因为如果掌握了递归的方法和技巧，会发现这是一个非常棒的编程思路。

那么，递归算法在日常编程中有哪些例子呢？

（1）汉诺塔游戏（如图6-1所示）。

（2）树结构的定义（如图6-2所示）。

图6-1　汉诺塔游戏

图6-2　树结构的定义

（3）谢尔宾斯基三角形（如图6-3所示）。

（4）女神自拍（如图6-4所示）。

说了这么多，在编程上，递归是什么这个概念还没讲呢！递归，从原理上来说就是函数调用自身的行为。你没听错，在函数内部可以调用所有可见的函数，当然也包括它自己。

图6-3　谢尔宾斯基三角形

图6-4　女神自拍

举个例子：

这个例子尝试了初学者玩递归最容易出现的错误。从理论上来讲，这个程序将永远执行下去直至耗尽所有内存资源。不过Python 3出于“善意的保护”，对递归深度默认是有限制的，所以上面的代码才会停下来。不过如果是编写网络爬虫工具，可能会“爬”得很深，那样的话就需要自行设置递归的深度限制了。方法如下：

     >>> import sys
     >>> sys.setrecursionlimit(10000)  # 将递归深度限制设置为一万层

上面的例子由于错误地使用递归，一不小心就把Python给“干掉了”，可见递归的威力之大。使用sys.setrecursionlimit(10000)虽然可以设置递归的深度，但如果设置的值太大（如100000000），那么程序也可能会崩溃，这时可以通过Ctrl+C快捷键让Python强制停止。

6.5.2　写一个求阶乘的函数

正整数的阶乘是指从1乘以2乘以3乘以4一直乘到所要求的数。例如所要求的数是5，则阶乘式是1×2×3×4×5，得到的积是120，所以120就是5的阶乘。好，那大家先自己尝试下实现一个非递归版本：

程序实现结果如下：

     >>>
     请输入一个正整数：5
     5 的阶乘是：120

普通函数的实现相信大家都会写，那再来演示一下递归版本：

以前没接触过递归的小伙伴肯定会怀疑这是否能正常执行？没错，这完全符合递归的预期和标准，所以函数无疑可以正确执行并返回正确的结果，程序实现结果与非递归版本的结果是一样的：

     >>>
     请输入一个正整数：5
     5 的阶乘是：120

麻雀虽小，却五脏俱全。这个例子满足了递归的两个条件：

•　调用函数本身。

•　设置了正确的返回条件。

请看详细分析，如图6-5所示。

图6-5　递归函数的实现分析

最后要郑重地说一下“普通程序员用迭代，天才程序员用递归”这句话是不无道理的。但是不要理解错了，不是说会使用递归，把所有能迭代的东西用递归来代替就是“天才程序员”了，恰好相反，如果你真的这么做的话，那你就是“乌龟程序员”啦。为什么这么说呢？不要忘了，递归的实现可是函数自己调用自己，每次函数的调用都需要进行压栈、弹栈、保存和恢复寄存器的栈操作，所以在这上面是非常消耗时间和空间的。

另外，如果递归一旦忘记了返回，或者错误地设置了返回条件，那么执行这样的递归代码就会变成一个无底洞：只进不出！所以在写递归代码的时候，千万要记住口诀：递归递归，归去来兮！

因此，结合以上两点致命缺陷，很多初学者经常就会在论坛上讨论递归存在的必要性，他们认为递归完全没必要，用循环就可以实现。其实这就像是在讨论C语言好还是Python更优秀一样，是没有必要的。因为一样东西既然能够持续存在，那必然有它存在的道理。递归用在妙处，代码自然简洁、精练，所以说“天才程序员使用递归”。

6.5.3　一帮小兔子——斐波那契数列

视频讲解

按理来说，今天的话题与兔子不搭边，不过大家也知道小甲鱼的风格——天南地北总能将看似无关的东西扯到一起，所以本节就讲讲如何用递归实现斐波那契（Fibonacci）数列。

斐波那契数列的发明者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci）。当年这个数列是由兔子交配的故事开始讲起的：假如说兔子在出生两个月后，就有了繁殖能力，此后这对兔子在接下来的每个月都能生出一对可爱的小兔子。假设所有兔子都不会老去，就这么一直折腾下去，那么一年以后可以繁殖多少对兔子出来呢？

我们都知道兔子繁殖能力是惊人的，如图6-6所示。

图6-6　斐波那契数列

数据统计如表6-1所示。

表6-1　斐波那契数列

可以用数学函数来定义，如下：

假设需要求出经历了20个月后，总共有多少对小兔子，不妨考虑一下分别用迭代和递归如何实现？

迭代实现：

接下来看看递归的实现原理，如图6-7所示。

图6-7　递归实现斐波那契数列的原理

递归实现：

可见逻辑非常简单，直接把所想的东西写成代码就是递归算法了。不过，之前总说递归如果使用不当，效率会很低，但是有多低呢？这就来证明一下。我们试图把20个月修改为35个月，然后试试看把程序执行起来。

发现了吧，用迭代代码来实现基本是毫秒级的，而用递归来实现就考验你的CPU能力啦（N秒~N分钟不等）。这就是小甲鱼不支持大家所有东西都用递归求解的原因，本来好好的一个代码，用了递归，效率反而拉下了一大截。

为了体现递归正确使用的优势，下一节来谈谈利用递归解决汉诺塔难题。如果不懂得递归，试图想要写个程序来解决问题是相当困难的，但如果使用了递归，你会发现问题奇迹般得变简单了！

6.5.4　汉诺塔

视频讲解

汉诺塔（如图6-8所示）的来源据说是这样的：一位法国数学家曾经编写过一个印度的古老传说。说的是在世界中心贝拿勒斯的圣庙里边，有一块黄铜板，上面插着三根宝针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。然后不论白天或者黑夜，总有一个僧侣按照下面的法则来移动这些金片：“一次只移动一片，不管在哪根针上，小片必须在大片上面。”规则很简单，另外僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

图6-8　汉诺塔

要解决一个问题，大家说什么最重要？没错，思路！思路有了，问题就可以随之迎刃而解。

对于游戏的玩法，可以简单分解为三个步骤：

（1）将前63个盘子从X移动到Y上，确保大盘在小盘下。

（2）将最底下的第64个盘子从X移动到Z上。

（3）将Y上的63个盘子移动到Z上。

这样看上去问题就简单一点了，有读者会说小甲鱼你这不废话嘛，说与没说一样！因为步骤（1）和步骤（3）应该如何执行才是让人头疼的问题。

但是仔细思考一下，在游戏中，我们发现由于每次只能移动一个圆盘，所以在移动的过程中显然要借助另外一根针才可以实施。也就是说，步骤（1）需要借助Z将1~63个盘子移到Y上，步骤（3）需要借助X将Y针上的63个盘子移到Z针上。

所以把新的思路聚集为以下两个问题：

问题一，将X上的63个盘子借助Z移到Y上。

问题二，将Y上的63个盘子借助X移到Z上。

然后我们惊奇地发现，解决这两个问题的方法与刚才第一个问题的思路是一样的，都可以拆解成三个步骤来实现。

问题一（将X上的63个盘子借助Z移到Y上）拆解为：

（1）将前62个盘子从X移动到Z上，确保大盘在小盘下。

（2）将最底下的第63个盘子移动到Y上。

（3）将Z上的62个盘子移动到Y上。

问题二（将Y上的63个盘子借助X移到Z上）拆解为：

（1）将前62个盘子从Y移动到X上，确保大盘在小盘下。

（2）将最底下的第63个盘子移动到Z上。

（3）将X上的62个盘子移动到Y上。

说到这里，是不是发现了什么？没错，汉诺塔的拆解过程刚好满足递归算法的定义，因此，对于如此难题，使用递归来解决，问题就变得相当简单。

参考代码：

看，这就是递归的魔力：

     >>>
     请输入汉诺塔的层数：3
     X --> Z
     X --> Y
     Z --> Y
     X --> Z
     Y --> X
     Y --> Z
     X --> Z