FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の再帰関数を実行したとき、戻り値はどれか。ここで÷は整数除算である。 ○整数型: g…
問題
次の再帰関数を実行したとき、戻り値はどれか。ここで÷は整数除算である。
○整数型: g(整数型: n)
if (n = 0)
return 0
endif
整数型: t ← g(n ÷ 2)
if (n mod 2 = 0)
return t ＋ n
else
return t × 2 ＋ 1
endif
g(13) を呼び出す。- ア 13
- イ 17
- ウ 19（正解）
- エ 21
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：19
g(13)はすぐに13を処理するのではなく、先にg(6)，g(3)，g(1)，g(0)まで降りていきます。戻るときに、偶数ならt+n，奇数ならt×2+1を使います。
| n | t=g(n÷2) | 戻り値 |
|---|---|---|
| 1 | 0 | 1 |
| 3 | 1 | 3 |
| 6 | 3 | 9 |
| 13 | 9 | 19 |
したがってg(13)=19です。nが奇数か偶数かを、各段階の戻りで判定するのがポイントです。
選択肢の見分け方：13は元の引数をそのまま答えにした値、17や21は奇数分岐の2倍処理を1段ずらすと出やすい値です。各段のnとtを分けてメモすることが重要です。
計算量と再帰の深さ：この関数は毎回nを半分（n÷2）にして呼び出すため、再帰の深さはnのビット数、すなわち約log₂n回でとどまります。g(13)では13→6→3→1→0と4回潜って戻るだけで答えが出ます。各段の処理は一定時間なので、計算量はO(log n)です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。