応用情報技術者 2011年 秋期 午前2 問07
問題文
個の正の整数が並んだ線形リストをで表し、空リストは[]で表す。次のように再帰的に定義される関数を、を実引数として呼び出したとき、print文によって表示される数字はどれか。ここで、プログラム中の=は等号、:=は代入を表す。
〔関数の定義〕
(1) first()はを返す。
(2) butfirst()は[]を返す。butfirst()は[]を返す。
(3) max(、)は、であればを返し、そうでなければを返す。
func(L)
begin
if L = [] then return0;
A := first(L);
B := func(butfirst(L));
C := max(A,B);
print C;
returnC;
end
選択肢
ア：123
イ：133
ウ：223
エ：233（正解）
再帰関数funcの動作解析【午前2 解説】
要点まとめ
- 結論：func([1,3,2])のprint出力は「233」となる。
- 根拠：funcはリストの先頭要素と再帰呼び出しの最大値を比較し、最大値をprintしながら返す。
- 差がつくポイント：再帰の戻り値とprintのタイミングを正確に追うことが重要で、処理順序を誤ると誤答につながる。
正解の理由
funcは空リストで0を返し、それ以外は先頭要素Aと残りのリストのfunc結果Bの最大値Cを計算し、Cをprintして返します。
L=[1,3,2]の場合、再帰は以下のように展開されます。
L=[1,3,2]の場合、再帰は以下のように展開されます。
- func([1,3,2]) → A=1, B=func([3,2])
- func([3,2]) → A=3, B=func([2])
- func([2]) → A=2, B=func([])
- func([]) → 0を返す
ここで、func([2])はmax(2,0)=2をprintし2を返す。
func([3,2])はmax(3,2)=3をprintし3を返す。
func([1,3,2])はmax(1,3)=3をprintし3を返す。
printはfunc([2])→2、func([3,2])→3、func([1,3,2])→3の順に実行されるため「233」となります。
よって正解はエです。
よくある誤解
- 再帰の戻り値だけを追い、printの順序を逆に考えてしまう。
- max関数の比較結果を誤解し、printする値を間違える。
解法ステップ
- 空リストの場合は0を返すことを確認する。
- リストの先頭要素Aを取得し、残りのリストでfuncを再帰呼び出しBを得る。
- AとBの最大値Cを計算し、printする。
- Cを返す。
- 入力リストの各段階でprintされる値を順に追い、最終的な出力を決定する。
選択肢別の誤答解説
- ア: 「123」→printの順序を先頭から順に単純に並べた誤り。実際は再帰の戻り値順にprintされる。
- イ: 「133」→func([2])のprintが2ではなく3と誤認。
- ウ: 「223」→func([1,3,2])のprintが1ではなく2と誤認。
- エ: 「233」→正しい再帰展開とprint順序を踏まえた正解。
補足コラム
再帰関数の理解には「呼び出し順」と「戻り値の処理順」の区別が重要です。
特にprint文が戻り値の直後にある場合、再帰の戻り値が計算されてからprintされるため、出力順は呼び出しの逆順になります。
この問題はリスト処理と再帰の基本を押さえる良問です。
特にprint文が戻り値の直後にある場合、再帰の戻り値が計算されてからprintされるため、出力順は呼び出しの逆順になります。
この問題はリスト処理と再帰の基本を押さえる良問です。
FAQ
Q: なぜprintは「233」の順に出力されるのですか？
A: 再帰呼び出しが深くなるほどprintは後から実行されるため、最も深い呼び出しから順にprintされます。
A: 再帰呼び出しが深くなるほどprintは後から実行されるため、最も深い呼び出しから順にprintされます。
Q: max関数の役割は何ですか？
A: 先頭要素と残りリストの最大値を比較し、より大きい値を返すことでリスト全体の最大値を求めています。
A: 先頭要素と残りリストの最大値を比較し、より大きい値を返すことでリスト全体の最大値を求めています。
関連キーワード: 再帰関数、リスト処理、最大値探索、プログラム解析、出力順序
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！