FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の再帰関数を実行したとき、戻り値はどれか。 ○整数型: p…
問題
次の再帰関数を実行したとき、戻り値はどれか。
○整数型: p(整数型: n)
if (n = 0)
return 0
elseif (n mod 2 = 0)
return p(n ÷ 2) ＋ 1
else
return p(n - 1) ＋ 2
endif
p(11) を呼び出す。- ア 7
- イ 8
- ウ 9（正解）
- エ 10
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：9
奇数ならn-1へ進んで2を足し、偶数ならn÷2へ進んで1を足します。p(11)はp(10)+2，p(10)はp(5)+1というように、偶奇で進み方が変わります。
| n | 分岐 | 戻り値 |
|---|---|---|
| 1 | 奇数 | 2 |
| 2 | 偶数 | 3 |
| 4 | 偶数 | 4 |
| 5 | 奇数 | 6 |
| 10 | 偶数 | 7 |
| 11 | 奇数 | 9 |
呼出し回数ではなく、戻るときに加算される1または2を積み上げます。
選択肢の見分け方：7はp(10)で止めた値、8や10は奇数で+2する箇所を1回ずらすと出やすい値です。偶数は半分、奇数は1減らすという経路を先に書くとよいでしょう。
計算量の目安：偶数では値が半分になり、奇数でも1減らすと次は必ず偶数になって半分へ進むため、2回以内で値が半減します。したがって再帰の深さはおよそ log₂ n に比例し、p(11)では7回の呼出しで0に到達します。nが大きくても呼出し回数が緩やかにしか増えない点が、この処理の特徴です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。