再帰と分割統治法

再帰は関数が自分自身をより小さい問題へ適用し、分割統治法は問題を部分問題へ分割して解き、その結果を統合する設計法です。

■ 試験で押さえるポイント

• 再帰処理には終了する基本ケースと、問題規模を必ず基本ケースへ近づける再帰ケースが必要です。

• 呼出しごとに引数、局所変数、戻り先をスタックへ積むため、深過ぎる再帰はスタックオーバーフローを起こします。

• 分割統治は分割・統治・結合の段階からなり、マージソート、クイックソート、2分探索等へ使われます。

• 同じ部分問題を繰り返す場合はメモ化・動的計画法を検討し、末尾再帰は処理系がループへ最適化できる場合があります。

■ 選択肢での判断ポイント

再帰では基本ケースと、問題を縮小してそこへ到達することを必ず確認します。分割統治は部分解を独立に求めて統合する点が重要です。

例: マージソートは配列を半分ずつに分け、要素1個まで再帰的に整列し、二つの整列済み列をマージします。