前言
上一篇写了关于数学归纳法的一些概念，那么这一篇就该带大家去体会一下递归了。
正文
这一篇主要通过一个小游戏带领大家走入递归的世界，这个游戏叫做汉诺塔 ，先说下游戏规则，如下图所示，有三根柱子，我们需要把套在 A 柱子上的圆环全部移动到 B 上，一次只能移动一个圆环，当然圆环的顺序也得一样。那么 C 柱则起到了中转的作用。
汉诺塔
下面是最终需要达到的结果
最终结果
有点人可能会说，一开始就让我们接触这么多的圆环，怎么也会搞混啊，那么我们就先从简单一点的开始吧。先从只有三个的圆环入手。
三个圆环
这里我们需要把 A 上的三个圆环借助 C 全部移动到 B 柱上。首先开始之前我们应该思考下，要想把三个全部移动到 B 柱上，则先需要把上面两个拿到 C 柱，然后把最大的那个拿到 B 柱，最后把上面的两个放到最大的上面。当我们把两个环拿到 C 的时候，势必需要借助 B 柱作为一个临时中转，这样我们就完成了移动的过程。写成规范一点的步骤就是：
步骤一： 把两个环从 A 柱经过 B 柱进行中转移动到 C 柱。
步骤二： 把第三个环拿到 B 柱。
步骤三： 把两个环从 C 柱经过 A 柱进行中转移动到 B 柱。
经过这三个步骤我们就实现了三个圆环的移动。这时候我们就可以结合上一篇讲过的数学归纳法进行递推到如果有 n 个圆环怎么移动的问题了。
首先，如果 n = 0 ，不做任何移动。
其次，如果 n > 0 ，做三个步骤：
步骤一： 把 n - 1 个环从 A 柱经过 B 柱进行中转移动到 C 柱。
步骤二： 把第 n 个环拿到 B 柱。
步骤三： 把 n - 1 个环从 C 柱经过 A 柱进行中转移动到 B 柱。
至于如何把 n - 1 个圆环移动，上面通过两个环的例子已经给大家进行了简单的说明，这就是递归和数学归纳法的不同之处了，数学归纳法是先知道简单的怎么做去推导出一般的结论，而递归则是知道一般的要求，通过把一般的问题化成简单的问题来解决。如果大家光听理论有些混乱的话，可以去玩玩汉诺塔的小游戏体会下
当然最后我们得从程序员的角度去实现一下汉诺塔的解法
#include<stdio.h>
#include<stdlib.h>
void hanoi(int n,char x,char y,char z);
int main()
{
hanoi(6,'A','B','C');
getchar();
return 0;
}
void hanoi(int n,char x,char y,char z)
{
if(n == 0)
{
//不做任何动作
}
else
{
hanoi(n-1,x,z,y);
printf("%c -> %c\t",x,y);
hanoi(n-1,z,y,x);
}
}
运行结果
我们可以通过游戏对程序的结果进行验证，在下一篇中会对这个游戏有个简短的总结。
这一篇通过一个小游戏带大家粗略了解了递归的概念，后面还将有两个例子和一个总结对递归进行了解。
网友评论