プログラミング学習における最大の難所の一つ「再帰関数」。その仕組みを理解するのに最も適した題材が「ハノイの塔」です。
この記事では、C言語を用いた実戦的な分割コンパイル構成のソースコードを解説します。コードをコピー＆ペーストして実際に動かしながら、アルゴリズムの正体を解き明かしましょう。
ハノイの塔：3つの基本ルール
ハノイの塔は、以下のルールを守って円盤を移動させるパズルです。
- 一度に動かせるのは1枚だけ。
- 小さな円盤の上に大きな円盤を置いてはいけない。
- 3本の柱（軸）を使い、全ての円盤を別の柱へ移動させればクリア。
【全コード】分割コンパイルで実装する
保守性の高いプログラムにするため、ヘッダーファイルを含む3つのファイルに分けて実装します。
1. hanoi.h（ヘッダーファイル）
関数の宣言を行い、メインプログラムから呼び出せるようにします。
#ifndef __Hanoi
#define __Hanoi
void hano1_main();
#endif2. hanoi.c（アルゴリズム本体）
再帰呼び出しの核心部分です。move関数の中で自分自身を呼び出し、複雑な移動を処理します。
#include<stdio.h>
void move(int no,int x,int y){
if(no>1)
move(no-1,x,6-x-y);
printf("\n円盤[%d]を%d軸から%d軸へ移動\n",no,x,y);
if(no>1)
move(no-1,6-x-y,y);
}
int hano1_main(void){
int n;
printf("ハノイの塔\n円盤の枚数：");
scanf("%d",&n);
move(n,1,3);
return 0;
}3. HanoiTest.c（実行用メインルーチン）
ユーザーが操作を選択するインターフェース部分です。列挙型（enum）を使用してメニューの状態を管理しています。
#include<stdio.h>
#include"hanoi.h"
typedef enum{
TERMINATE,Hanoi1
}Menu;
Menu SelectMenu(void){
int ch;
do
{
printf("(1)ハノイの塔 (0)終了");
scanf("%d",&ch);
} while (ch< TERMINATE || ch>Hanoi1);
return (Menu)ch;
}
int main(void){
Menu menu;
do
{
switch (menu = SelectMenu())
{
case Hanoi1:
hano1_main();
break;
}
} while (menu != TERMINATE);
return 0;
}実行結果
アルゴリズムの鍵：魔法の式「6 - x - y」
このプログラムの最もスマートな点は、中継地点の軸番号を求める 6 - x - y という計算式です。
3本の軸（1, 2, 3）の合計値は 1 + 2 + 3 = 6 になります。そのため、「現在の軸（x）」と「目的の軸（y）」が分かれば、残りの軸（中継地点）は必ず 6 - x - y で算出できるのです。
現在の軸(x) | 目的の軸(y) | 計算式 (6-x-y) | 中継地点(残りの軸) |
1軸 | 3軸 | 6 - 1 - 3 | 2軸 |
1軸 | 2軸 | 6 - 1 - 2 | 3軸 |
2軸 | 3軸 | 6 - 2 - 3 | 1軸 |
この工夫により、煩雑な条件分岐を使わずに、シンプルで美しいコードを実現しています。
図で追う：円盤3枚のときの再帰の展開
言葉だけでは追いにくいので、円盤 3 枚（move(3, 1, 3)）を実行したときに move がどう分解され、どの順で printf が呼ばれるかを図にしました。
ポイントは、1 回の move が「小さい問題 → 自分の出力 → 小さい問題」の 3 ステップに分かれることです。この構造がそのまま繰り返されるため、円盤 n 枚のときの手数は 2ⁿ - 1 になります。3 枚なら 7 手、10 枚なら 1023 手です。
後日談：十数年前に書いた同じコードは、今の環境では通らなかった
ここまでのコードは現在の環境で動くよう整えたものですが、この題材には後日談があります。PC 内の古いファイルを整理していたところ、高校時代のプログラミング実習で書いた「ハノイの塔」のソースコードが出てきたので、十数年ぶりにコンパイルし直してみました。
結果として、当時のコードはそのままでは通りませんでした。原因は主に次の 2 つです。
- 必要なヘッダの読み込みが不足していて、
printfの暗黙の関数宣言が通らない - 引数の型を K&R 形式（関数名の後に型を並べる古い書き方）で書いている
当時のコード（抜粋）
hanoi(n, from, via, to)
int n;
char from, via, to;
{
if (n == 0) return;
hanoi(n - 1, from, to, via);
printf("円盤%dを %c -> %c へ移動\n", n, from, to);
hanoi(n - 1, via, from, to);
}プロトタイプ宣言に書き直したコード
#include <stdio.h>
void hanoi(int n, char from, char via, char to) {
if (n == 0) {
return;
}
hanoi(n - 1, from, to, via);
printf("円盤%dを %c -> %c へ移動\n", n, from, to);
hanoi(n - 1, via, from, to);
}
int main(void) {
hanoi(4, 'A', 'B', 'C');
return 0;
}書き直して実行すると、円盤が軸の間を移動していく様子がそのまま出力されます。
なぜ当時は通っていたのか
暗黙の関数宣言は、1999 年の C 標準改訂（C99）で削除された機能です。GCC も 13 までは警告にとどめて後方互換を保っていましたが、GCC 14 からは既定でエラーとして報告され、出力ファイルが作られません。この変更は GCC 14 の移行ガイドに明記されています。当時のコンパイラでは通っていたコードが今は通らないのは、この積み重ねによるものです。
一方、K&R 形式の関数定義については、同ガイドに「C23 が既定の言語仕様になった後も当面サポートを続ける見込み」と書かれています。つまりこちらは「エラーになるから直す」のではなく、引数の型チェックを効かせるためにプロトタイプ宣言へ書き換える、という位置づけになります。
再帰を手で追える題材としての価値
モダンな言語は高度に抽象化されていて、裏側の仕組みを知らなくても書いたとおりに動きます。対して C 言語は、メモリやスタックの動きを直接意識させます。ハノイの塔の再帰処理は、まさにスタックが積まれて戻っていく様子をコードで追体験する題材です。
生成 AI でコードを書く速度が上がった今、価値が移っているのは出てきたコードが正しいかを判断できる力のほうです。その判断を支えるのは結局のところ基礎知識で、こうした題材を手で追う時間はその土台になります。
手元でビルドして動かす
3 つのファイルを同じディレクトリに置き、まとめてコンパイルします。
# 使っているコンパイラを確認する（出力されたバージョンは控えておく）
gcc --version
# 3ファイルをまとめてビルドする
gcc -std=c17 -Wall -o hanoi hanoi.c HanoiTest.c
# 実行（メニューで 1 を選ぶと円盤の枚数を聞かれる）
./hanoi本記事のコードはプロトタイプ宣言で書いてあるため、GCC・Clang のどちらでも上記のコマンドでビルドできます。gcc --version の出力を控えておくと、前述の GCC 14 での挙動変更に該当する環境かどうかを後から判断できます。
まとめ
ハノイの塔は、「大きな問題を小さな問題に分解する」というプログラミングの本質を教えてくれます。まずは円盤3枚の設定で動かし、プログラムがどのように自分自身を呼び出しているか（再帰）を追いかけてみてください。
同じコードでも、書かれた時期のコンパイラと今のコンパイラでは通る・通らないが変わります。古いコードを動かし直す作業は、言語仕様が何を捨ててきたかを具体的に知る機会にもなります。