汉诺塔是经典的递归问题，也有非递归解法，此处只讨论递归解法

1、游戏描述如下：

        A、B、C 三个桌子，其中A桌子上放了几个大小不同的盘子，盘子的排列顺序为： 从上到下，依次从小到大递增；现要求把这些盘子从 A 桌子上移动到 C 桌子上，盘子移动时有一点要求：每次移动必须保证三张桌子上大盘子在下、小盘子在上；

2、游戏步骤：

        1）当 A上有1个盘子时，只需要将A上的盘子移至C

        2）当A上有2个盘子时，将A的1号盘子移动至B，再将A的2号盘子移至C，最后将B上的1号盘子移至C

        3）当A上有3个盘子时，先借助C将1、2号盘子从A移至B，然后将3号盘子移动到C，最后借助A将B上的1、2号盘移至C

        4）综上可知：当A上有N（N>1）个盘子时，先借助C将A上1至n-1号盘子（共n-1个）移至B，再将A上的n号盘子移至C，最后借助A将B上的n-1个盘子移至C盘。

3、算法描述

        美国一位学者发现了一种简单的算法，只需要轮流两步操作就能实现：

        首先把三个桌子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在桌子A上，根据圆盘的数量确定桌子的排放顺序：

        （1）若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。

        （2）按顺时针方向把圆盘1从现在的桌子移动到下一个桌子，即当n为偶数时，若圆盘1在桌子A，则把它移动到B；若圆盘1在桌子B，则把它移动到C；若圆盘1在桌子C，则把它移动到A。

        （3）接着，把另外两个桌子上可以移动的圆盘移动到新的桌子上。即把非空桌子上的圆盘移动到空桌子上，当两根桌子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，但是可实施的行动是唯一的。

        （4）反复进行（2）（3）操作，最后就能按规定完成汉诺塔的移动。

4、Python代码实现

#!/usr/bin/env python# _*_ coding:utf-8 _*_def input_n():        while True:        n = raw_input('请输入A上的盘子个数:')        try:            n = int(n)            if n < 1:              print '请输入大于0的整数!'            else:              break        except Exception, e:            print '请不要随意输入字符!'            return n  def move_info(n, from_table, to_table):        step_info = '将%s号盘:%s ----> %s' % (n, from_table, to_table)    return step_info    def recursion_hano(n, a, b, c, step_info_list = []):        if n == 1:  # 当n=1时，直接将盘子移动至目的桌，递归终止条件        step_info_list.append(move_info(1, a, c))            else:        recursion_hano(n-1, a, c, b)  # 先借助C将A上n-1个盘子移至B        step_info_list.append(move_info(n, a, c))  # 将A最后一个盘子移动到C        recursion_hano(n-1, b, a, c)  # 借助A将B上的n-1个盘子移至C        return step_info_list    def main():        n = input_n()      step_info_list = recursion_hano(n,'A', 'B', 'C')    for i,k in enumerate(step_info_list):        print '第%s步:%s' % (i+1, k)    if __name__ == '__main__':    main()

5、其他

        当盘子为N时，移动次数为 2^N - 1