今回は、基本情報技術者試験の令和8年度 科目B 公開問題 問3を例に、再帰関数の読み解き方を解説します。
再帰関数とは
再帰関数とは、関数の中で自分自身を呼び出す関数のことです。
一見すると複雑そうですが、基本的な仕組みを理解すれば、それほど難しいものではありません。
再帰関数を見つけたら、まずは次の2点に注目しましょう。
- 処理を終了させる条件はどこにあるのか？
- 自分自身を呼び出すとき、引数はどう変化しているのか？
再帰関数は、自分自身を繰り返し呼び出すことができます。しかし、終了する条件がなければ、呼び出しが終わらなくなってしまいます。
そのため、最初に終了条件を確認することが重要です。
例題：令和8年度 科目B 問3
出典：令和8年度 基本情報技術者試験 科目B 公開問題 問3
次のプログラム中の□ に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1 から始まる。
関数func1 に与える引数と，関数func2 に与える引数とが同じとき，二つの関数は同じ値を返す。プログラムでは，配列の領域外を参照してはならないものとする。
〔プログラム〕
○整数型: func1(整数型: n)
if (nが2以下)
return 1
endif
return 2 × func1(n － 2) ＋ func1(n － 1)
○整数型: func2(整数型: n)
整数型の配列: data ← {1, 1, 1}
整数型: i
/* nが3より小さいときは繰返し処理を実行しない */
for (iを3からnまで1ずつ増やす)
data[1] ← data[2]
data[2] ← data[3]
data[3] ← □
endfor
return data[3]
解答群
ア 2 × data[1] ＋ data[2]
イ 2 × data[2] ＋ data[1]
ウ 2 × data[i － 1] ＋ data[i － 2]
エ 2 × data[i － 2] ＋ data[i － 1]
オ data[3] ＋ 2 × data[1] ＋ data[2]
カ data[3] ＋ 2 × data[2] ＋ data[1]
キ data[3] ＋ 2 × data[i － 1] ＋ data[i － 2]
ク data[3] ＋ 2 × data[i － 2] ＋ data[i － 1]
今回の問題では、次のような再帰関数が登場します。
○整数型: func1(整数型: n)
if (nが2以下)
return 1
endif
return 2 × func1(n － 2) ＋ func1(n － 1)
まず終了条件を確認しましょう。
n <= 2 の場合は、1を返して処理を終了します。
つまり、nが1または2の場合は、これ以上自分自身を呼び出しません。
次に、再帰処理の部分に注目します。
return 2 × func1(n － 2) ＋ func1(n － 1)
ここでは、自分自身を2回呼び出しています。
func1(n - 2)：2つ前の値func1(n - 1)：1つ前の値
つまり、2つ前の値を2倍して、1つ前の値を加えるという計算です。
n=5の場合を考えてみよう
いきなりn=5の計算を追いかけると、再帰呼び出しが何度も登場して複雑に感じるかもしれません。
そこで、n=1の場合から順番に考えてみましょう。
まず、n=1とn=2の場合は終了条件によって1が返されます。
次にn=3の場合です。
2 × func1(1) + func1(2)
すでにfunc1(1)とfunc1(2)はどちらも1と分かっています。
したがって、2×1+1=3です。
同じようにn=4、n=5も計算してみます。
| n | 計算 | 結果 |
|---|---|---|
| 1 | 終了条件 | 1 |
| 2 | 終了条件 | 1 |
| 3 | 2×1+1 | 3 |
| 4 | 2×1+3 | 5 |
| 5 | 2×3+5 | 11 |
このように、n=1から順番に考えると、データの変化が簡単に見えてきます。
再帰関数だからといって、最初から複雑な呼び出しの流れをすべて追いかける必要はありません。
まず終了条件を確認し、確定している値から順番に計算していく。
これが再帰関数を読み解くためのポイントです。
再帰関数とループ処理
ここまで理解できれば、もうひとつ重要なことに気づきます。
今回の再帰関数が行っている計算は、ループ処理でも表現できるということです。
必要なのは、直前の2つの値だけです。
つまり、直前の2つの値を保持しながら、順番に新しい値を求めていけば、再帰関数と同じ結果が得られます。
今回の問題では、この考え方が重要になります。
まとめ
再帰関数は難しいものだと思われがちですが、まずは次のことを意識してみましょう。
- 自分自身を呼び出している部分を探す
- 処理が終了する条件を確認する
- 引数がどのように変化するかを読み取る
- 小さな値から順番に結果を確認する
大切なのは、プログラムの書き方を暗記することではなく、どのようにデータが変化しているのかを理解することです。
再帰関数もループ処理も、データの変化を理解するという点では同じです。