简   介

这里     从汉诺塔游戏Hanoi Tower中了解背后递归的数学思想，并使用python来实现

01 汉诺塔效果演示

这个程序图形编程并不是小朋友做的。程序分为两部分，用算法求出移动的步骤，并调用python的tkinter库把移动步骤用图形的方式显示出来。需要源代码的同学，请私信邮箱。另外，这个程序所用的递归算法略显啰嗦，递归算法部分可以采用本文后面介绍的算法。

02 基础知识

在程序中递归的基础是函数。了解函数之后则需要了解递归的概念，以及如何寻找递归规律的方法。

1F

函数

在python中，函数的定义遵循的语法是 def 函数名(参数)：。函数可以有返回值也可以不带返回值。如果有返回值则使用return关键字返回。我下面用左手举个栗子：

def函数名(参数):

....

....

...

return返回值

之所以存在函数，是因为函数把经常执行的功能给封装起来，方便后续调用，减少工作量。

2F

递归和寻找递归规律的方法

寻找规律的方法就是从简单的情况入手，逐渐变复杂，进而探求其中的规律。寻找递归规律的方法也是如此，由简单入手，通过画图辅助，来寻找其中的规律。

学习知识得挑好欺负的下手(删除)从简单的开始学习。比如，给出一个数字，打印出这个数字到一的所有数字。一般而言，使用while语句(for也可以)。下面这个我用右手举得栗子，是增加了函数的使用，以及奇偶数判断的最终结果。

defMaxprint(num):

ifnum%2==0:

print(str(num)+" is an even number")

else:

print(str(num)+" is an odd number")

i=8whilei>0:

Maxprint(i)

i=i-1

如果不使用while等循环语句呢，如果实现同样的的功能。从下面的图左侧部分可以看出，每一个数，都是先打印自己，然后再打印上一个数到1的所有数字。

我们先假设已经存在一个打印函数mp(num)，可以打印num到1的所有数字。这一点很重要，不假设这个函数已经存在，我们根本无法进行后续的讨论。这种假设结果已经存在的思想非常有用，比如在是否实现某个目标的问题上，我们可以假设这个目标已经实现，在这种情况下，你个人会有什么不同，会有什么得失。考虑完这些，你个人基本能够想明白是否要花费时间和精力来实现这个目标。

还好没跑远。。。。

在有了mp(num)函数已经实现的前提下，我们可以发现两点：第一点是每一个数都是由打印自己print(num)和打印比自己小1的数的序列mp(num-1)组成。第二点是存在一个特殊的数字，即1，它只需要打印自己。

程序实现如下。很简单有木有！！！如果想要输出8到1，只需要使用mp(8)即可。

defmp(num):

ifnum==1:

print(num)

else:

print(num)

mp(num-1)

03 汉诺塔的实现

1F

汉诺塔的规律

要寻找规律，则必须要抽象成为数学模型。寻找一种合适的语言或者规则定义来描述这个模型就很重要。一个5层高的塔包括5层，分别是1，2，3，4，5，而这个5层高的塔就是G5。在这个定义下，G3表示1，2，3这三层组成的一组。从G1开始，只需要把1这层从p1移到p3。在这里移动过程，我们使用print来代替。从G2开始，则都需要借助p2，总共移动三大步。先把最底下那层以外的所有层都先移动到p2，再把最底层移动到p3(使用print)，然后把在p2上的所有层移动到p3。

因此，我们假设已经存在一个移动函数move(源柱子，目标柱子，G组，中间辅助柱子)。因此，除了G1特殊外，其他的G组都是包括三大步：

move(源柱子，中间辅助柱子，G-1组，目标柱子)

把G组中的最大那个(刚好数值也等于G，例如8层塔的最大那个是第8层)从源柱子移动到目标柱子(print)

move(中间辅助柱子，目标柱子，G-1组，源柱子)

2F

程序实现defmove(pS,pD,Gnumber,pM):

ifGnumber==1:

print(pS+"-->"+pD+" : "+str(Gnumber))

else:

move(pS,pM,Gnumber-1,pD)

print(pS+"-->"+pD+" : "+str(Gnumber))

move(pM,pD,Gnumber-1,pS)

是不是同样的很简单！！！

如果是5层的话，运行结果如下。如果想要记录所有移动过程的话，可以使用列表来记录每一次移动(列表的append方法)，每一次的移动都可以记录成为一个三个元素的列表，例如 p1–>p3:2可以记录为[1，3，2]，即【源柱子，目标柱子，第几层】。从而整个记录列表是一个二次列表。

p1-->p2 : 1p1-->p3 : 2p2-->p3 : 1p1-->p2 : 3p3-->p1 : 1p3-->p2 : 2p1-->p2 : 1p1-->p3 : 4p2-->p3 : 1p2-->p1 : 2p3-->p1 : 1p2-->p3 : 3p1-->p2 : 1p1-->p3 : 2p2-->p3 : 1

04 关于图形的实现

图形的实现简单的说几句，包括以下三点。。。

图形使用tkinter库来实现，汉诺塔的层都是使用button控件动态创建，控件的长度都是对应的层数值。为了方便寻找和控制层，我们使用了列表来作为层数的名称。例如一个5层的塔，我们使用了一个5元列表b。其中第三层的名字就是b[2] (因为列表下标都是从0开始)。关于移动方法，比如[1，3，2] (p1–>p3:2)，在这里第二层的名字是b[1]，我们就把b[1]这个button控件的位置参数改变，使得其从1号柱子移动到3号柱子。