递归：汉诺塔详解

昨天有的同学问到我关于汉诺塔的问题，说是无法理解。且不说汉诺塔这是个经典递归算法问题，光是中学的数学课，我们应该就见过不只一次这个问题。

首先我们来回顾一下中学的数学问题：现在有一个汉诺塔，上面有 $n$ 个盘子，请问要几步才能完成这个汉诺塔的移动？

我们假设最终要 $a_n$ 步。那么，我们先来试试看：

$n=1$

这个时候想要完成任务，只需要把这个盘子从 $X$ 移动到 $Z$ 就可以了。

于是， $a_1=1$
$n=2$

这个时候，我们需要把最小的先放入中转站，然后把大的移动到 $Z$ ，最后再把中转站的也移到 $Z$ 。

于是， $a_2=3$
$n=3$

现在盘子越来越多，不着急。我们先把上面的两个按照 $n=2$ 的方法来移动到中转站。

然后将最大的移动到 $Z$ ，然后再将中转站上的所有移动到 $Z$ 。

于是， $a_3=7$

然后我们再回顾下，会发现，除了第一次，其他的不论多少个盘子，都是将除了最大的以外所有盘子先移动到中转站，然后把最大的移动到 $Z$ ，最后再把中转站上的所有盘子移到 $Z$ 上。

因此， $a_n$ 我们都可以通过它的上一次的移动来推出。每一次的移动，都要把其中 $n-1$ 个从 $X$ 到 $Y$ ，然后从 $Y$ 到 $Z$ ，相当于 $a_{n-1}$ 两遍，最大的那个从 $X$ 到 $Z$ 移动一次。

故 $a_n=2a_{n-1}+1$ 。

是不是越听越像递归了？

好，那我们现在来从程序的角度理解下。

首先，只有一个盘子的时候，不需要用到中转站，直接X --> Z即可。

两个以上盘子的时候，我们需要引入一个中转站Y，首先让n-1个执行X --> Y（中转缓存），然后让最大的执行X --> Z，最后让那n-1个执行Y --> Z（清空缓存）。

至于这n-1个盘子怎么操作，递归就好了。

原理知道了，那我们来创建一个函数：

hanoi(盘子数, 起点, 中转站, 终点)

这里的起点，中转站和终点，在每一轮里是不一样的，比如，执行中转缓存的时候，本质上是X --> Y，那么起点就是X，终点就是Y，中转站当然就是Z了。

只有一个盘子的时候，直接：

print(X,'-->',Z)

多个盘子的时候：

hanoi(n-1, X, Z, Y) # 把除了最大的都移动到Y，此时Z是中转站（中转缓存）
print(X,'-->',Z) # 把最大的那个从A移动到Z
hanoi(n-1, Y, X, Z) # 把除了最大的那些从Y移动到Z，此时X是中转站（清空缓存）

说到这里应该都明白了。下面是代码示例：

C语言：

void hanoi(int n, char X, char Y, char Z)
{
    if (n == 1)
    {
        printf("%c --> %c\n", X, Z);
    }
    else
    {
        hanoi(n-1, X, Z, Y);
        printf("%c --> %c\n", X, Z);
        hanoi(n-1, Y, X, Z);
    }
}

Java：

public void hanoi(int n, String X, String Y, String Z) {
    if (n == 1) {
        System.out.println(X + "-->" + Z);
    }
    else {
        hanoi(n-1, X, Z, Y);
        System.out.println(X + "-->" + Z);
        hanoi(n-1, Y, X, Z);
    }
}

Python：

def hanoi(n:int, X:str, Y:str, Z:str):
    if n == 1:
        print(f"{X} --> {Z}")
    else:
        hanoi(n-1, X, Z, Y)
        print(f"{X} --> {Z}")
        hanoi(n-1, Y, X, Z)

Go：

func hanoi(n int, X string, Y string, Z string) {
    if (n == 1) {
        fmt.Println(X + "-->" + Z)
    } else {
        hanoi(n-1, X, Z, Y)
        fmt.Println(X + "-->" + Z)
        hanoi(n-1, Y, X, Z)
    }
}

感谢您的支持，我会继续努力的!