基本情報技術者試験「再帰」の問題
次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
○整数型: f(整数型: n)
if (n が 1 以下)
return 1
endif
return n + f(n - 2)ア21
イ110
ウ1110
エ111
正解
エ．111
n が 1 以下になるまで n を 2 ずつ減らして加算する。20→18→…→2→0 の経路で偶数列 20+18+16+14+12+10+8+6+4+2=110 を加え、基底 f(0)=1 を足すと 111 となるため エが正しい。
?選択肢ごとの解説
ア ×最初の n=20 のみを加え基底値 1 を足した 21 であり、中間の f(18)…f(2) の寄与を落とした誤りである。
イ ×加算した偶数列 20+18+…+2=110 のみとし基底値 1 を落とした off-by-one 的な誤りである。
ウ ×展開の桁を取り違え、各段の値を誤って連結・累乗的に膨らませた 1110 とする桁数の誤りである。
エ ○n が 1 以下になるまで n を 2 ずつ減らして加算する。20→18→…→2→0 の経路で偶数列 20+18+16+14+12+10+8+6+4+2=110 を加え、基底 f(0)=1 を足すと 111 となるため エが正しい。
✎くわしく
再帰では『基底条件で何を返すか』と『各段で何を加えるか』を分けて管理する。基底値の取り扱いを誤ると合計が 1 ずれる典型ミスが生じる。
✓本番での押さえどころ
試験のコツ
再帰は呼び出しを末端まで展開してから戻り値を内側から代入し直すと確実である。
覚え方
『行きで分解、帰りで合算』と唱え、最深部の基底値から戻る。
よくある誤り
基底 f(0)=1 を忘れて 110 とするミスが多い。
アルゴリズムとプログラミングの他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0004