Java与C++分别用递归实现汉诺塔详解

Java与C++分别用递归实现汉诺塔详解

1. 理论背景

汉诺塔是一个经典的递归问题，它可以用于验证一个编程语言是否具备递归能力。

汉诺塔由三根针和若干个圆盘组成，每个圆盘有一个固有的大小，这些圆盘可以滑动到任意一根针上，但是每次只能移动一个圆盘并且大的圆盘不能放在小的圆盘上面。使用递归的方式可以让我们轻松找出三个针上的圆盘移动方法。

2. 递归实现

Java实现

public class Hanoi {
    public void move(int n, char from, char to, char mid) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + from + " to " + to);
        } else {
            move(n - 1, from, mid, to);
            System.out.println("Move disk " + n + " from " + from + " to " + to);
            move(n - 1, mid, to, from);
        }
    }
}

这个 Java 代码中的 move 方法使用了 3 个参数：圆盘的数量 n 和三个针 from, to, mid。如上面所述，当 n 等于 1 时，只需要将当前针上编号为 1 的圆盘移动到目标针即可。当 n 大于 1 时，将编号大于 1 的圆盘移动到辅助针上，再将编号为 1 的圆盘移到目标针上，最后将编号大于 1 的圆盘从辅助针移到目标针上。

C++实现

#include <iostream>

using namespace std;

void move(int n, char from, char to, char mid) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
    } else {
        move(n - 1, from, mid, to);
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
        move(n - 1, mid, to, from);
    }
}

int main() {
    int n = 3;
    char A = 'A';
    char B = 'B';
    char C = 'C';
    move(n, A, C, B);
    return 0;
}

这个 C++ 代码也是与上面 Java 的方式实现类似，也是使用递归，当 n 等于 1 时输出移动的指令， n 大于 1 时出错移动。

3. 示例说明

示例一

有 4 个圆盘需要从 A 柱移到 C 柱，则输出：

Java实现：

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 4 from A to C
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

C++实现：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Move disk 4 from A to B
Move disk 1 from C to B
Move disk 2 from C to A
Move disk 1 from B to A
Move disk 3 from C to B
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B

示例二

需要将5个圆盘从A柱移到C柱，则输出：

Java实现：

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 4 from A to C
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 5 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 3 from C to A
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 4 from C to B
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

C++实现：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Move disk 4 from A to B
Move disk 1 from C to B
Move disk 2 from C to A
Move disk 1 from B to A
Move disk 3 from C to B
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 5 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Move disk 3 from B to A
Move disk 1 from C to B
Move disk 2 from C to A
Move disk 1 from B to A
Move disk 4 from B to C
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C