数据结构的递归1

本文主要通过一个叫《河内之塔》的小游戏带领大家进入递归世界。先说游戏规则。如下图所示，有三根柱子。我们需要将支柱A上的所有环移动到B上，一次只能移动一个环。当然，环的顺序必须是一样的。那么C柱就起到了中转的作用。

下面是要达到的最终结果

可能有人会说，刚开始接触那么多环，怎么会迷茫呢？那我们就从简单的开始吧。让我们从三个戒指开始。

这里我们需要用c的方式把A柱上的三个环全部移动到B柱上，首先在开始之前，我们要想好。如果我们想把三个都移到B柱上，我们需要把上面的两个移到C柱上，然后把最大的一个移到B柱上，最后把上面的两个放到最大的一个上。当我们把两个环拿到C的时候，就需要用B柱作为临时中转，这样我们就完成了搬家的过程。编写标准点的步骤是:

第一步:通过B柱将两个环从a柱转移到C柱。

第二步:拿第三环去B柱。

第三步:通过a柱将两个环从C柱转移到B柱。

经过这三步，我们实现了三环运动。这时候就可以结合上一篇文章提到的数学归纳法，推导出如果有n个环，如何移动的问题。

首先，如果n = 0，什么都不做。

第二，如果n > 0，执行三个步骤:

步骤1:将n-1环从A列通过B列转移到C列..

第二步:拿第n环去B柱。

第三步:通过a柱将n-1环从C柱转移到B柱。

至于如何移动n-1环，上面两个环的例子已经给大家简单解释过了。这就是递归和数学归纳法的区别。数学归纳法是知道如何先做简单的事情来推导出一般的结论，而递归是知道一般的要求，把一般的问题变成简单的问题来解决。如果只是听理论有点迷茫，可以玩个河内塔的小游戏体验一下。

当然，最终还是要从程序员的角度来实现汉诺塔的求解

我们可以通过游戏来验证程序的结果，我们会在下一篇文章中对游戏进行简要的总结。

本文通过一个小游戏让你对递归的概念有个大概的了解，后面是两个例子和一个总结来理解递归。