ハノイの塔の問題を C 言語の再帰アルゴリズムで実装する方法

次は、C言語版のハノイの塔問題を再帰アルゴリズムを使用した実装例です。

#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3; // 将三个盘子从A移动到C
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

ネイティブな日本語で言い換えると、

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

このアルゴリズムは、再帰の考え方を用いて問題をより小さなサブ問題に分解します。まず n-1 枚の円盤を最初の柱 (from) から補助柱 (aux) に移動させ、その後最大の円盤を最初の柱 (from) から最後の柱 (to) に移動させ、最後に n-1 枚の円盤を補助柱 (aux) から最後の柱 (to) へ移動します。再帰呼び出しによって、問題の規模を縮小し、最終的に 1 枚の円盤だけを移動するまで続けます。