応用情報技術者 2013年 秋期 午前2 問08
問題文
再帰的に定義された手続 procで、proc(5) を実行したとき、印字される数字を順番に並べたものはどれか。
proc(n)
n=0 ならば戻る
そうでなければ
{
nを印字する
proc(n-1)を呼び出す
nを印字する
}
を実行して戻る
選択肢
ア：543212345
イ：5432112345（正解）
ウ：54321012345
エ：543210012345
再帰的手続きprocの動作解析【午前2 解説】
要点まとめ
- 結論：proc(5)の出力は「5432112345」となる。
- 根拠：nを印字→proc(n-1)呼び出し→nを印字の順で再帰的に処理されるため、数字が折り返す形で現れる。
- 差がつくポイント：再帰呼び出しの前後でnを印字するため、中央に0は一度だけ現れ、数字の並びが左右対称になる点を理解すること。
正解の理由
proc(n)はnが0になるまで再帰的に呼び出され、呼び出し前にnを印字し、呼び出し後にもnを印字します。
proc(5)の場合、5→4→3→2→1→0の順に呼び出され、0で戻り、戻りながら数字を印字します。
このため、5から1まで降順に印字され、0は印字されず、戻りながら1から5まで昇順に印字されます。
よって「5432112345」が正しい出力です。
proc(5)の場合、5→4→3→2→1→0の順に呼び出され、0で戻り、戻りながら数字を印字します。
このため、5から1まで降順に印字され、0は印字されず、戻りながら1から5まで昇順に印字されます。
よって「5432112345」が正しい出力です。
よくある誤解
0も印字されると誤解しやすいですが、n=0のときは印字せずに戻るため、0は出力に含まれません。
また、再帰呼び出しの前後で印字する順序を混同し、数字の並びを誤ることがあります。
また、再帰呼び出しの前後で印字する順序を混同し、数字の並びを誤ることがあります。
解法ステップ
- proc(5)を呼び出す。n=5なので0でないため処理継続。
- n=5を印字 → 「5」
- proc(4)を呼び出す。
- n=4を印字 → 「54」
- proc(3)を呼び出す。
- n=3を印字 → 「543」
- proc(2)を呼び出す。
- n=2を印字 → 「5432」
- proc(1)を呼び出す。
- n=1を印字 → 「54321」
- proc(0)を呼び出す。n=0なので戻る（印字なし）。
- n=1を印字 → 「543211」
- 呼び出し元に戻り、n=2を印字 → 「5432112」
- 同様にn=3→「54321123」、n=4→「543211234」、n=5→「5432112345」
- 最終的に「5432112345」が出力される。
選択肢別の誤答解説
- ア: 543212345
→ 0を印字しない点は正しいが、数字の折り返し部分が1つ少なく、戻りの印字が不足している。 - イ: 5432112345
→ 正解。再帰呼び出し前後の印字順序と0の扱いが正確。 - ウ: 54321012345
→ 0を印字しているため誤り。0のときは印字せずに戻る。 - エ: 543210012345
→ 0を2回印字している誤り。0は印字されない。
補足コラム
再帰処理は「呼び出し前後の処理順序」と「終了条件の扱い」が理解の鍵です。
今回のように「呼び出し前後で同じ処理を行う」パターンは、左右対称の出力や木構造の巡回でよく見られます。
また、0を印字しない終了条件は、再帰の基底ケース（ベースケース）として重要な役割を果たします。
今回のように「呼び出し前後で同じ処理を行う」パターンは、左右対称の出力や木構造の巡回でよく見られます。
また、0を印字しない終了条件は、再帰の基底ケース（ベースケース）として重要な役割を果たします。
FAQ
Q: なぜ0は印字されないのですか？
A: procの定義でn=0のときは「戻る」だけで印字処理がないため、0は出力されません。
A: procの定義でn=0のときは「戻る」だけで印字処理がないため、0は出力されません。
Q: 再帰呼び出しの前後で印字する意味は？
A: 呼び出し前に印字することで降順、呼び出し後に印字することで昇順の数字列が形成され、左右対称の出力になります。
A: 呼び出し前に印字することで降順、呼び出し後に印字することで昇順の数字列が形成され、左右対称の出力になります。
関連キーワード: 再帰、手続き、出力順序、基底条件、プログラミング、アルゴリズム
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！