JINTORI : 再帰呼び出しサンプル

再帰呼び出しを利用したサンプルプログラムとして作成したもの。
$ jintori 40 30 20
などとして実行します。 (40% の率でランダムに通路を設けたマップを 30 x 20 コマのサイズで作る)
タイトル図のような画像ウィンドウが表示されますので、通路(白)をクリックしてください。 上下左右に連続している通路を再帰的に調べて塗りつぶしていきます。 塗りつぶしの様子をアニメーションで見せていますが、これが「探索」の様子を表しています。 exit ボタンを押せば終了します。
プログラミングC」の教材では「自己相似的な図形を再帰的に描く」ということを再帰処理の例として取り上げましたが、それらを含めて「再帰的に定義するのが都合がよい」場面にはなかなか遭遇しないものです。 むしろもうひとつの利用例である「探索」の方が、実際のプログラミングで遭遇する再帰呼び出しを利用する場面としてはありそうに思います。 このサンプルはまさに「探索」を行うものです。 自分の上下左右の通路を踏みに行き、「そこが踏めた(カベではなく通路だった)」場合には再びその場所の上下左右を踏むように再帰的に呼び出しています。 プログラムとしては gomap() 関数にあたります。
void gomap(int p, int w, int h)
{
  if(map[w][h] != -1 ) return; // そこは通路じゃないので行けません
  map[w][h]=p; // 踏めたので自分の色で染めておく
  drawmap(p); msleep(100); // アニメーション的に再描画
  gomap(p, w-1, h);  // 左
  gomap(p, w+1, h);  // 右
  gomap(p, w, h-1);  // 上
  gomap(p, w, h+1);  // 下 へ踏んでみる
  return;
}
踏めればどんどん上下左右に進める。 踏めなかったら単に戻る。 この記述で「しらみつぶしに踏めるところをぜんぶたどる」処理が実現できていることが納得できるでしょうか?

<<Back
Yutaka Yasuda (yasuda@cc.kyoto-su.ac.jp)