平成25年度 秋期 午前 問8
アルゴリズム
再帰に関する問題
再帰的に定義された手続 proc で，proc(5) を実行したとき，印字される数字を順番に並べたものはどれか。
proc(n)
n=0 ならば戻る
そうでなければ
{
n を印字する
proc(n−1) を呼び出す
n を印字する
}
を実行して戻る- ア543212345
- イ5432112345
- ウ54321012345
- エ543210012345
答えと解説を見る
✓ これが正解イ5432112345
解説
呼ぶ前と戻った後に印字するので、出力は10桁の回文になります。
設問は、再帰的に定義された手続を 5 で呼び出したときに印字される数字の並びを選ばせています。見る軸は二つで、止まる条件のところで何を印字するかと、印字が呼出しの前後に一つずつ置かれていることです。まず、引数が 0 のときは何も印字せずに戻ると書かれているので、この値は出力に現れません。つぎに、引数が 0 でないときは、自分の値を印字し、一つ小さい引数で自分を呼び、戻ってからもう一度同じ値を印字します。そこで小さい方から積み上げると、1 で呼べば 11、2 で呼べば 11 の前後を 2 で挟んで 2112、3 で呼べば 321123、4 で呼べば 43211234 となり、5 で呼べば 5432112345 になります。この作りから出力は必ず前後対称になり、桁数は呼出し 1 回につき 2 文字ずつ増えるので引数の 2 倍、すなわち 10 桁です。実際、前から読んでも後ろから読んでも 54321 と並び、桁数も 10 で合致します。
ほかの選択肢はなぜ違うのか
- ア543212345：9 桁しかなく、中央にあるはずの二つ続きの 1 が一つに減っています。前後で対称にならないので、行きと帰りで同じ値を出す作りと合いません。
- ウ54321012345：11 桁あり、中央に 0 が一つ入っています。引数が 0 の呼出しでも印字してから戻ると読んだ形ですが、その場合は印字より前に戻ってしまいます。
- エ543210012345：12 桁あり、中央に 0 が二つ入っています。引数が 0 のときも行きと帰りの両方で印字すると読んだ形で、余分な 2 文字が中央に増えています。
出典：平成25年度 秋期 応用情報技術者試験 午前 問8
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）