平成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

 ア  123  イ  133  ウ  223  エ  233


答え エ


解説
func(L )のL = [1, 3, 2]を求めると
L = [ ]でないので、A1がfirst([1, 3, 2])でA = 1になる。
また、B1はfunc(butfirst([1, 3, 2]))なので、func([3, 2])を求めると
 L = [ ]でないので、A2がfirst([3, 2])でA = 3になる。
 また、B2はfunc(butfirst([3, 2]))なので、func([2])を求めると
  L = [ ]でないので、A3がfirst([2])でA = 2になる。
  また、B3はfunc(butfirst([2]))なので、func([ ])を求めると
   L = [ ]でなので、return 0になる。
  すなわち、B3 = 0で、C3 = max(A3, B3) = max(2, 0) = 2でprint文で2を表示し、return 2になる。
 したがって、B2 = 2になり、C2 = max(A2, B2) = max(3, 2) = 3でprint文で3を表示し、return 3になる。
したがって、B1 = 3になり、C1 = max(A1, B1) = max(1, 3) = 3でprint文で3を表示し、return 3になる。
結果、表示される数字は233(エ)になる。


キーワード
・再帰的処理

キーワードの解説
  • 再帰的処理(recursive)
    処理(関数)の中で自分自身の処理を呼び出すことです。
    再帰を使用することで、処理を単純に表すことができます。

もっと、「再帰的処理」について調べてみよう。

戻る 一覧へ 次へ