再帰の応用の演習

再帰を用いて複雑なプログラムをシンプルに書くことができます

問題によっては分割統治法によって効率よく問題を解くことができます

カッコの対応チェック

( ( ( ) ( ) ) ( ) ( ) ( ( ( ) ) ( ) ) )

複雑なカッコの列が入力されたとき、対応が正しいか、そうでないかを判定する。

考えかた : 内側から、対応するカッコはないものとして取り除いてゆき、もっとも外側のカッコが対応していればよい。その途中で対応しないカッコ、すなわち1）開きだけ、2）閉じだけ、のどちらかがあれば対応していないことになる。

１）開き括弧なら

つぎの文字以降対応するカッコを読み飛ばす : 再帰

飛ばしたあとが閉じ括弧なら ok で一文字先へのポインタ/添字を返す

２）閉じ括弧なら

対応しないので ng で戻る

マージソート

6 8 1 7 3 4 5 2　をマージソートする

１）データ集合を半分に分ける

6 8 1 7 と 3 4 5 2

２）それぞれソート（マージソート）する : 再帰

1 6 7 8 と 2 3 4 5

３）二つの集合をマージする

1 2 3 4 5 6 7 8

参考