過去問解きまくり研究所

平成23年度 秋期 午前 問7

基礎理論

再帰に関する問題

n 個の正の整数 x1, x2, …, xn が並んだ線形リストを [x1, x2, …, xn] で表し，空リストは [ ] で表す。次のように再帰的に定義される関数 func(L) を，L＝[ 1, 3, 2 ] を実引数として呼び出したとき，print 文によって表示される数字はどれか。ここで，プログラム中の＝は等号，:＝は代入を表す。

〔関数の定義〕
 (1) first([x1, x2, …, xn]) は x1 を返す。
 (2) butfirst([x1, x2, …, xn]) は [x2, …, xn] を返す。butfirst([x]) は [ ] を返す。
 (3) max(x, y) は，x≧y であれば x を返し，そうでなければ y を返す。

func(L)
begin
    if L ＝ [ ] then return 0;
    A :＝ first(L);
    B :＝ func(butfirst(L));
    C :＝ max(A, B);
    print C;
    return C;
end
答えと解説を見る

✓ これが正解エ233

解説

表示は奥へ進むときではなく戻る途中です。

この関数は自分自身を呼び出す再帰の形で定義されています。読み解く要は、表示の命令がどこに置かれているかの一点です。表示は、自分自身を呼び出してその戻り値を受け取った後に置かれています。つまり奥へ進むときではなく、手前へ戻る途中で行われます。ですから、いちばん奥の呼び出しから順に数字が出てきます。実引数は三つの数からなる線形リストです。関数はまず先頭の要素を取り、残りのリストで自分自身を呼びます。これを繰り返すと、リストが空になったところで 0 を返して折り返します。空のときは表示しないという点も見落とせません。折り返してからは、その段で取った先頭の要素と、奥から返ってきた値のうち大きいほうを表示して返します。いちばん奥の段は先頭が 2 で奥からの値が 0 なので 2、その手前は先頭が 3 で奥からの値が 2 なので 3、最も手前は先頭が 1 で奥からの値が 3 なので 3 です。並べると 233 になります。この関数が返す値は、その位置から後ろにある数の最大値になるので、表示される数字は手前へ進むほど大きくなるか同じ値のままで、小さくなることはありません。

ほかの選択肢はなぜ違うのか

出典：平成23年度 秋期 応用情報技術者試験 午前 問7

この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）