今天我们来介绍常见的算法——递归。

递归函数

递归是什么？ 简单地说，递归就是通过不断调用自己来完成持续循环的过程。

虽然概念可能有点复杂，但我会写递归函数来说明。 众所周知，斐波那契数列从第三项开始。 每一个都是前面两个项的和。

一、一、二、三、五、八、十三、二十一……。

我们用递归的思想实现上面的数列。

设递归函数为f(x )。 写递归函数时，请注意两点。

一是给出基本情况，这里的基本情况是f(1)=1，f ) )2)=1。

第二，决定规则。 这里的规则是f(x )=f(x-1 ) f ) x-2 )。

现在，可以创建函数了：

好了，到此结束！ 感觉很简单吧？ 让我们简单分析一下上面的代码：

首先，我们定义了一个叫f(x )的函数。 def是define的缩写，意思是定义。 f(x )的x是项数，表示几个项目。 例如如果你想知道斐波那契数列的五个项目是什么，x=5。

其次，由于f(1)和f )2)的值都是1，所以可以将这些合并到x=2的条件中返回1。

最后，在x2时，返回前两项的和。 只有此时的f(x-1 )和f ) x-2 )才有意义。

说了这么多你可能会怀疑，但是让我们举个例子来看看上述代码的执行过程。

例如，假设您想知道f(5)的值。 因为是52，所以返回前两项的和f )4) f )3)。

f(4)和f )3)各是多少？ 让我们先来看看f(3)。 因为是32，所以返回f )2) f )1)=1)=2。 让我们看看f(4)。 因此，我们将返回到： f )3) f )2)=[f )2) f )1)=1)1=3。

因此，f(5)=f )4) f )3)=3)2=5。 让我们调用我们写的函数进行验证：

让我们来看看

汉诺塔

递归实用化——汉诺威的游戏。

如上图所示，有3个zydny、b、c，其中a有3个大小不同的圆环，越往下的圆环越大。 我们的目标是按照现在的顺序把三个圆盘从a移到c。 其中，有两个规则限制。

1 .一次只能移动一个圆盘。

2 .大圆盘不能放在小圆盘上。

让我们先从简单的情况来看。 如果只有一个圆盘，那很简单。 把圆盘从a直接移动到c就可以了。

两个圆盘的情况怎么样？ 我们画个图说明一下：

如上图所示，有一两个圆盘。 要把2号圆盘移动到c，首先需要移动1号圆盘。 那一天我应该搬到哪里？ 为了清楚起见，1号可以移动到b，下一步2号可以直接移动到c。1号移动到c，2号需要先去b，然后再去c。 因此，最快的方法是将1移动到b。

然后，我们可以把2号圆盘移到c

最后，只需要把1号圆盘从b移到c

现在，让我们总结一下移动两个圆盘的步骤。 一共需要三个步骤。 在第一步中，将小圆盘从a移动到b。 第二步，将大圆盘从a移动到c； 第三步，把小圆盘从b移动到c。 我们必须记住这三个步骤。 这是之后推理的基础。

接下来，让我们来看看三个圆盘的情况。

让我想想。 要将三个圆盘从a移动到c，首先需要将三号上面的圆盘1和2移动到b。 那样的话，3号就可以直接到c了。

关键时刻到了。 我们把一两个圆盘移到b上，不是我们之前讨论过的两个圆盘的情况吗？ 只是，上一个目标是从a移动到c，现在是从a移动到b。 同样是空着的两根棍子。 只是号码不同，本质上没有什么不同。

理解了上述核心内容，我们的想法就清楚了。 三个圆盘也同样可以看作三大步骤。 将步骤1、1和2转移到b； 将步骤2、3移动到c将步骤3、1和2从b移动到c。 其中，1和2是如何移动到b或c的，这是之前讨论过的两个圆盘的情况，这是递归的思想。

再扩展一下上面的例子，如果是n个圆盘呢？

如上图所示，a有n个圆盘。 按这个顺序移动到c

就像把大象放进冰箱需要三步一样，我们也只需要三步。 第1步，将a中的1到n-1个圆盘移动到b。 步骤2，将a中剩下的第n个圆盘移动到c； 步骤3，将b中的n-1个圆盘移动到c中。 关于将n-1个圆盘移动到b的方法，请重复上述步骤，直到递归到熟悉的2个或3个圆盘所需的移动步骤。

是的，这就是今天的一切。 欢迎参加消息讨论。