平成25年 秋期 応用情報技術者 午前 問8

再帰的に定義された手続きprocで、proc(5)を実行したとき、印字される数字を順番に並べたものはどれか。

 proc(n )
  n = 0ならば戻る
  そうでなければ
  {
    n を印字する
    proc(n - 1)を呼び出す。
    n を印字する
  }
  を実行して戻る

 ア  543212345  イ  5432112345
 ウ  54321012345  エ  543210012345


答え イ


解説
proc(5)を実行したときの動作をトレースします。

  • proc(5)を実行すると、引数が0でないので、5を印字し、proc(5-1) = proc(4)を呼び出します。
    • proc(4)を実行すると、引数が0でないので、4を印字し、proc(4-1) = proc(3)を呼び出します。
      • proc(3)を実行すると、引数が0でないので、3を印字し、proc(3-1) = proc(2)を呼び出します。
        • proc(2)を実行すると、引数が0でないので、2を印字し、proc(2-1) = proc(1)を呼び出します。
          • proc(1)を実行すると、引数が0でないので、1を印字し、proc(1-1) = proc(0)を呼び出します。
            • proc(0)を実行すると、引数が0なので、そのまま終了します。
          • proc(1)の残りの処理として、1を印字し終了します。
        • proc(2)の残りの処理として、2を印字し終了します。
      • proc(3)の残りの処理として、3を印字し終了します。
    • proc(4)の残りの処理として、4を印字し終了します。
  • proc(5)の残りの処理として、5を印字し終了します。
したがって、印字結果は、5 4 3 2 1 1 2 3 4 5(イ)になります。


キーワード
・再帰呼び出し

キーワードの解説
  • 再帰呼び出し(recursive call)
    関数が自身の処理の中で、自分自身を呼び出し実行することです。
    再帰呼び出しでプログラムを記述すると、見た目がすっきりするというメリットがありますが、実際の動作は関数を呼び出すためにスタックが消費されたり、関数の呼び出しに時間がかかるのでそれほどのメリットはありません。
    再帰呼び出しの例としてはパズルのハノイの塔やクイックソートがあります。

もっと、「再帰呼び出し」について調べてみよう。

戻る 一覧へ 次へ