汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

后来，这个传说就演变为汉诺塔游戏，玩法如下:

• 1.有三根杆子A,B,C。A杆上有若干碟子

• 2.每次移动一块碟子,小的只能叠在大的上面

• 3.把所有碟子从A杆全部移到C杆上

分析：

如果n=1，则将圆盘从A直接移动到C。
如果n=2，则：
1.将A上的n-1(等于1)个圆盘移到B上；
2.再将A上的一个圆盘移到C上；
3.最后将B上的n-1(等于1)个圆盘移到C上。
  如果n=3，则：
A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，步骤如下：
(1)将A上的n`-1(等于1)个圆盘移到C上。
(2)将A上的一个圆盘移到B。
(3)将C上的n`-1(等于1)个圆盘移到B。
B. 将A上的一个圆盘移到C。
C. 将B上的n-1(等于2，令其为n`)个圆盘移到C(借助A)，步骤如下：
(1)将B上的n`-1(等于1)个圆盘移到A。
(2)将B上的一个盘子移到C。
(3)将A上的n`-1(等于1)个圆盘移到C。
   到此，完成了三个圆盘的移动过程。
    从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：
第一步  把A上的n-1个圆盘移到B上；
第二步  把A上的一个圆盘移到C上；
第三步  把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。

也许你已经发现规律了，即每次都是先将其他圆盘移动到辅助柱子上，并将最底下的圆盘移到c柱子上，然后再把原先的柱子作为辅助柱子，并重复此过程。

这个过程称为递归，即定义一组基本操作，这组操作将规模小一点（或大一点）的操作当做一个整体——无需关心它的细节，只当它已经完成了——然后执行剩下的操作。而在更小或更大的规模中也依此操作，直到规模达到预定值

在数学上，有些公式就是采用递归的方式定义的。例如阶乘和斐波那契数列（Fibonacci Sequence）。前者的公式为：

规定0!=1!=1，对于n>=2，有n!=n*(n-1)!

这里的n-1就是比n规模略小的阶乘，而1就是规模的最小值（预定值）（0是作为特殊值而专门规定的）。

著名的斐波那契数列定义如下，可以看出，f(n)是由规模更小一些的f(n-1)和f(n-2)推导出来的：

f(0)=0，f(1)=1
f(n)=f(n-1)+f(n-2) (n>=2)

因此，递归实际上就是用自己来定义自己。

回到前面汉诺塔的问题上来。我们假设函数func(n, a, b, c)用于将n个圆盘由a移动到c，b作为辅助柱子。那么我们可以这样实现这个递归过程：

ｊａｖａ代码实现

import java.util.Scanner;

public class ddd{
    static int count=1;//用来记录生成步骤的条数
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        move(n,"A","B","C");
    }
    /**
     * 将n个盘子从A移到B，C作为辅助的柱子
     * @param n 原来有多少个盘
     * @param A 原来放置盘子的柱子
     * @param B B柱子
     * @param C C柱子
     */
    public static void move(int n,String A,String B,String C) {
        if(n==1){
            System.out.println("第"+count+++"步:"+"将第1个盘从"+A+"移到"+B);
        }
            else{
            move(n-1,A,C,B);
            System.out.println("第"+count+++"步:"+"将第"+n+"个盘从"+A+"移到"+B);
            move(n-1,C,B,A);
        }
    };
        }

python代码实现

def move(n, a, b, c):
if n==1:
        print (a,'-->',c)
        return
    else:
        # 首先需要把 (N-1) 个圆盘移动到 b
        move(n-1,a,c,b)
        # 将a的最后一个圆盘移动到c
        move(1,a,b,c)
        # 再将b的(N-1)个圆盘移动到c
        move(n-1,b,a,c)  
move(4, 'A', 'B', 'C')

详细解释：

def move(n, a, b, c):
if n==1:
        print (a,'-->',c)
        return
    else:
        # 首先需要把 (N-1) 个圆盘移动到 b
        move(n-1,a,c,b)
        # 将a的最后一个圆盘移动到c
        move(1,a,b,c)
        # 再将b的(N-1)个圆盘移动到c
        move(n-1,b,a,c)  
move(4, 'A', 'B', 'C')'''
我把3个盘子的汉诺塔全部通过代码演示，
按缩进原则，每一个缩进即进一个递归函数，
每打印一次即中止当前递归,也就是每个print
说明:
 1.n = 3, n = 2, n = 1
 是每次执行if(n == 1)的结果，
 这里就不写判断了，相信大家也能看懂，
 也就是n不等与1时就减1进入递归
 2.请注意a,b,c柱每次进入函数的顺序，
 不要被形参带错路了，看准每次函数参数的实参
'''
move(3, "a", "b", "c")
n=3:
 #开始从a上移动n-1即2个盘子通过c移动到b,
 #以腾出c供a最后一个盘子移动
   move(2, "a","c","b")
  n=2:
 #开始进行n=2的一个递归，
 #把当前a('a')柱上的n-1个盘子
 通过c('b'）移动到b('c')
   move(1, "a", "b", "c")
  n=1:
 #n=2的第一个递归完成,打印结果，
 #执行当前子函数剩余代码
     print("a", "->", "c")
    move(1, "a", "c", "b")
  n=1:
       print("a", "->", "b")
    move(1, "c", "a", "b")
  n=1:
       print("c", "->", "b")
#到这里完成了a柱上面的n-1即是2个盘子的移动
#开始把a柱上最后一个盘子移动到c柱上
   move(1, "a", "b", "c")
  n=1:
       print("a", "->", "c")
#到这里完成移动a柱上的最后一个盘子到c柱上
   move(2, "b", "a", "c")
  n=2:
#开始进行n=2的第二个递归,
# 即把当前b('b')的盘子(n-1个)
# 通过a('a')移动到c('c')上
   move(1, "b", "c", "a")
   n=1:
#n=2 的第二个递归完成，
# 打印结果并执行当前子函数的剩余代码
     print("b", "->", "a")
    move(1, "b", "a", "c")
   n=1:
       print("b", "->", "c")
    move(1, "a", "b", "c")
   n=1:
       print("a", "->", "c")
# 到这里把b上的盘子通过a移

扩展：汉诺塔问题的非递归实现

这种算法看得我头疼，直接传送门吧

https://tieba.baidu.com/f?kz=1255166419&red_tag=3546780199

知识重在总结和梳理，只有不断地去学习并运用，才能化为自己的东西。由于本人进阶猿类时间尚短，故此公众号即是我学习，工作的笔记，也是和大家交流，相互提升技术的平台，希望大家不吝赐教。