再帰と分割統治

イントロ

流れを順番に追う

基本情報技術者試験で扱う「再帰と分割統治」を、IT知識なしでも意味と使いどころから学べるように整理します。まず目的をつかみ、似た言葉や条件の違いを短く見分けます。

定義

手順

構造図

図では、再帰と分割統治の流れを順に整理しています。入力、処理、判断、結果のつながりを確認します。

例

場面: 階乗をで計算し、n=1で止まる条件を確認する例
順に考えると: まず再帰が何を表すかを確認します。次に終了条件との違いを、問題文の対象・条件・順序から分けます。ここでは必ず小さくなる入力と終了条件があるかを見る。この順で読むと、初見の選択肢でも中心の考え方から外れた説明を除外しやすくなります。
ここが結論: この例では、必ず小さくなる入力と終了条件があるかを見ることが要点です。答えを選ぶときは、再帰呼出しが自動的にいつか止まると思うという読み違いを避けます。

注意

確認

Q1

再帰と分割統治を問題で読むとき、最も適切な見方はどれですか。

まとめ