本文共 1455 字，大约阅读时间需要 4 分钟。

1. 什么是汉诺塔问题

汉诺塔问题就是将A柱上n个圆全部移动到C上，过程中可以借助B柱，但要始终保持小圆在大圆上面

2. 如何写递归

我们都知道汉诺塔问题一般都是用递归来解决，那么递归到底该怎么写？

博主经过总结后，得出结论：
写上终止条件，并将距离目标最近的一层逻辑写出来就是递归！

一定要记住，我们不要深入跟进递归内部，只需将最近的一层逻辑写出来即可。

举例：递归问题之斐波那契数列

先看它的函数代码：

int fib(int n){   	if(n==1) return 1;	else if(n==2) return 1;	else return fib(n-1)+fib(n-2);}

这个求斐波那契数列第n项的fib函数就是由两部分组成：

1. 第一部分就是在n等于1或2时返回1，这是终止条件
2. 第二部分我们所要求的fib(n)——即第n项的值就等于第n-1项的值加上第n-2项的值（斐波那契数列的定义）；也就是说fib(n)的返回值就是fib(n-1)+fib(n-2)

就这么简单！

3. 汉诺塔问题的递归思路

汉诺塔函数的意思

函数声明如下：

void hanoi(int n, char a, char b, char c)

这个函数的意思就是：将a柱上的n个圆经由b柱移动到c柱上（即将第二个参数上的n个圆经由第三个参数移动到第四个参数上）

(汉诺塔问题需要用递归解决，只要是递归就由上面提到的两部分组成，我们先看第一部分)

第一部分：终止条件

如果柱子上的圆的数量n等于0了，自然也就终止了，那么终止条件就是

if(n==0) return;

第二部分：距离目标的最近逻辑

想要实现hanoi(n, 'A', 'B', 'C')，即实现将a柱上的n个圆经由b柱移动到c柱上，那么就要分三步：

1. 先将a柱上的n-1个圆经由c柱移动到b柱
2. 再将a柱上剩下的1个圆（也即最下方最大的圆）移动到c上
3. 最后将b柱上的n-1个圆经由a柱移动到c柱上

经过这三步就能将a柱上的n个圆经由b柱移动到c柱上

结合上面所说的汉诺塔函数的意思，我们可以得出：

1. 第一步等同于hanoi(n-1,a,c,b)
2. 第二部的移动直接打印移动过程即可
3. 第三步等同于hanoi(n-1,b,a,c)

大家可能会问：之后怎么办呢？
答案当然是交给计算机了！递归的更深层次的逻辑是不需要我们去想，让代码“飞”一会儿就OK了

（正如斐波那契数列的所求项就是由它的前两项相加得到的，其它的不需要在代码上体现，计算机自己就会帮你搞定了！）

汉诺塔函数的代码

c语言

void hanoi(int n, char a, char b, char c){   	if(n==0) return;	hanoi(n-1,a,c,b);	print("%d:%c -> %c",step++,a,c);	hanoi(n-1,b,a,c);}

（step表示第几次移动）

Python

def hanoi(n, a, b, c):    global step    if n==0:        return    hanoi(n-1,a,c,b)    print("{}:{} -> {}".format(step,a,c))    step += 1    hanoi(n-1,b,a,c)

（step表示第几次移动）

这样就搞定了!

最后

如果看完了这篇文章觉博主讲解的还不错的话，能不能麻烦您点上一个宝贵的赞呢？十分感谢大家！