IT資格用語解説基本情報技術者試験・アルゴリズム設計

再帰と分割統治法

更新日:

用語解説

再帰は、関数の中で自分自身を呼び出し、問題をより小さな同じ形の問題にして解く方法です。分割統治法は、問題を小さく分けて解き、その結果をまとめて全体を解く設計の考え方です。

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

  • 再帰には、呼び出しを終える条件と、問題を小さくしてその条件に近づける処理が必要です。

  • 呼び出しのたびにスタックを使うため、再帰が深過ぎるとスタックがあふれます。

  • 分割統治法は、マージソートやクイックソートなどで使われます。

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

終了条件がない再帰は止まりません。問題が必ず小さくなるかを確認します。

例: マージソートは配列を半分ずつに分けて再帰的に並べ替え、整列した二つの列を一つにまとめます。

音声で聞く

この用語に関連する過去問

IT用語集トップへ戻る基本情報技術者試験の教科書を開く