再帰的アルゴリズムとは
再帰的アルゴリズムとは、関数が自分自身を呼び出すことで処理を進めるプログラミング技法です。通常の繰り返し構造（for文やwhile文）と異なり、再帰は「問題をより小さな同型の問題に分割し、最終的に基底条件（出口）に到達することで終了する」という考え方に基づいています。これにより、複雑な処理をシンプルで直感的な形に表現できるのが大きな特徴です。
オルビナ/基本情報技術者専門官その壱の再帰的アルゴリズムでは、再帰的アルゴリズムの基本について解説しています。理解をさらに深めたい方は、ぜひ下の関連記事も読んでみてくださいね。
総和（Sum）
function sum(n):
if n = 1 then return 1
else return n + sum(n-1)
ここまでは総和のコードを用意しました。これで総和を実行できます。sum(3) を呼び出すと
1. sum(3) = 3 + sum(2)
sum(3)の戻り値は、3 + sum(2)です。
2. sum(2) = 2 + sum(1)
sum(2)の戻り値は、2 + sum(1)です。
3. sum(1) = 1 （基底条件で終了）
sum(1)の戻り値は、1です。戻り計算すると、
sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6
最終結果は 6 です。このテーマは 令和元年秋期試験問11 でも実際に出題されています。再帰関数の問題は、コードをそのまま覚えるだけではなく、トレース問題として計算過程を正しく追えるかどうかが重要です。
つまり、呼び出しの流れを一歩ずつ展開し、基底条件に到達した後に戻りながら計算を整理できるかが合否を分けるポイントになります。
階乗（Factorial）
function factorial(n):
if n = 0 then return 1
else return n × factorial(n-1)
ここまでは総和のコードを用意しました。これで総和を実行できます。factorial(4)を呼び出すと
1. factorial(4) = 4 × factorial(3)
2. factorial(3) = 3 × factorial(2)
3. factorial(2) = 2 × factorial(1)
4. factorial(1) = 1 × factorial(0)
5. factorial(0) = 1 （基底条件で終了）出口から戻りながら計算すると
factorial(1) = 1 × 1 = 1
factorial(2) = 2 × 1 = 2
factorial(3) = 3 × 2 = 6
factorial(4) = 4 × 6 = 24
最終結果は 24 です。このテーマは 平成28年春期試験問7 でも実際に出題されています。
再帰関数の階乗問題では、単に結果を求めるだけでなく、乗算回数や再帰呼び出し回数を問う形式が多く見られます。
ここではあえて解説を加えず、まずは過去問をそのまま読んでみましょう。問題文を追うだけでも「どこで掛け算が行われ、何回再帰が呼ばれるのか」を意識できるはずです。
剰余（Modulo）
function hash(x, m):
return x mod m
ここまでは剰余のコードを用意しました。これで剰余を実行できます。例えば、入力値が 32、割る数が 10 の場合
32 ÷ 10 = 3 余り 2
となるので、
32 mod 10 = 2
この結果を添字として利用し、配列の「インデックス2」に 32 を格納します。今回のコードはハッシュ関数の例です。ハッシュ関数の場合は、2番の中に 32 を格納します。
このテーマは、ハッシュ探索アルゴリズム関連の過去問でも出題されています。ハッシュ法では、キーを剰余演算などで添字に変換して格納しますが、異なるキーが同じ添字に割り当てられる「衝突（collision）」が発生する可能性があります。
試験では「ハッシュ値の計算」だけでなく、衝突処理（collision handling）をどう行うかまで理解しているかが問われやすい分野です。線形探索法やチェイン法など、代表的な処理方法を押さえておくと安心です。
過去問でも頻出テーマなので、必ず確認しておきましょう。
コメント