C言語でハノイの塔を攻略！再帰関数と分割コンパイルを徹底解説

プログラミング学習における最大の難所の一つ「再帰関数」。その仕組みを理解するのに最も適した題材が「ハノイの塔」です。

この記事では、C言語を用いた実戦的な分割コンパイル構成のソースコードを解説します。コードをコピー＆ペーストして実際に動かしながら、アルゴリズムの正体を解き明かしましょう。

ハノイの塔：3つの基本ルール

ハノイの塔は、以下のルールを守って円盤を移動させるパズルです。

• 一度に動かせるのは1枚だけ。
• 小さな円盤の上に大きな円盤を置いてはいけない。
• 3本の柱（軸）を使い、全ての円盤を別の柱へ移動させればクリア。

【全コード】分割コンパイルで実装する

保守性の高いプログラムにするため、ヘッダーファイルを含む3つのファイルに分けて実装します。

1. hanoi.h（ヘッダーファイル）

関数の宣言を行い、メインプログラムから呼び出せるようにします。

#ifndef __Hanoi
#define __Hanoi

void hano1_main();

#endif

2. 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 で算出できるのです。

この工夫により、煩雑な条件分岐を使わずに、シンプルで美しいコードを実現しています。

まとめ

ハノイの塔は、「大きな問題を小さな問題に分解する」というプログラミングの本質を教えてくれます。まずは円盤3枚の設定で動かし、プログラムがどのように自分自身を呼び出しているか（再帰）を追いかけてみてください。