大滝本4.10について

waaさん(No.1)

大滝本の4.10について
再帰の問題なのですが、再帰の処理がいまいちよくわかっていません。
とくに一通りスタックに追加してからの、呼び出し元に戻るという部分の理解が曖昧です。

大滝本を持っている方、よければ再帰処理の流れを教えていただきたいです！

2025.10.30 12:57

jjon-comさん(No.2)

★FE プラチナマイスター

その本が手元にないので直接の回答ではありません。

再帰についてはこの掲示板で何度も話題になり、私も解説を投稿したことがあります。

https://www.fe-siken.com/bbs/5800.html のNo.4
https://www.fe-siken.com/bbs/5930.html のNo.8 No.9
https://www.fe-siken.com/bbs/5898.html のNo.5

2025.10.30 17:20

jjon-comさん(No.3)

★FE プラチナマイスター

stack[1] = {1, 2, 3}
stack[2] = {1, 2, 3}
stack[3] = {1, 2, 3}

○proc()
  if (stack[1]が空なら)
    /* 何もしない */
  else
    stack[1]からpopした値をstack[3]にpush
    proc()
    stack[3]からpopした値をstack[2]にpush
  endif

初回のproc()の呼び出し時は、stack[1]は空ではないのでelse句が実行されます。

＋ーーーー
｜（stack[1] = {1, 2, 3} で空ではないから次を実行）
｜stack[1]からpopした値をstack[3]にpush ★a
｜proc()
｜stack[3]からpopした値をstack[2]にpush
＋ーーーー

★aの実行後をイメージすると、stack[1] = {1, 2} になり空ではないので、入れ子のproc()の内容はこうなります。

＋ーーーー
｜（stack[1] = {1, 2, 3} で空ではないから次を実行）
｜stack[1]からpopした値をstack[3]にpush
｜＋ーーーー
｜｜（stack[1] = {1, 2} で空ではないから次を実行）
｜｜stack[1]からpopした値をstack[3]にpush ★b
｜｜proc()
｜｜stack[3]からpopした値をstack[2]にpush
｜＋ーーーー
｜stack[3]からpopした値をstack[2]にpush
＋ーーーー

★bの実行後をイメージすると、stack[1] = {1} になり空ではないので、さらに入れ子のproc()の内容はこうなります。

＋ーーーー
｜（stack[1] = {1, 2, 3} で空ではないから次を実行）
｜stack[1]からpopした値をstack[3]にpush
｜＋ーーーー
｜｜（stack[1] = {1, 2} で空ではないから次を実行）
｜｜stack[1]からpopした値をstack[3]にpush
｜｜＋ーーーー
｜｜｜（stack[1] = {1} で空ではないから次を実行）
｜｜｜stack[1]からpopした値をstack[3]にpush ★c
｜｜｜proc()
｜｜｜stack[3]からpopした値をstack[2]にpush
｜｜＋ーーーー
｜｜stack[3]からpopした値をstack[2]にpush
｜＋ーーーー
｜stack[3]からpopした値をstack[2]にpush
＋ーーーー

★cの実行後をイメージすると、stack[1] が空になるので、さらにさらに入れ子のproc()の内容は /* 何もしない */ です。

＋ーーーー
｜（stack[1] = {1, 2, 3} で空ではないから次を実行）
｜stack[1]からpopした値をstack[3]にpush
｜＋ーーーー
｜｜（stack[1] = {1, 2} で空ではないから次を実行）
｜｜stack[1]からpopした値をstack[3]にpush
｜｜＋ーーーー
｜｜｜（stack[1] = {1} で空ではないから次を実行）
｜｜｜stack[1]からpopした値をstack[3]にpush
｜｜｜＋ーーーー
｜｜｜｜（stack[1] = {} で空になったので）
｜｜｜｜/* 何もしない */
｜｜｜＋ーーーー
｜｜｜stack[3]からpopした値をstack[2]にpush
｜｜＋ーーーー
｜｜stack[3]からpopした値をstack[2]にpush
｜＋ーーーー
｜stack[3]からpopした値をstack[2]にpush
＋ーーーー

結果として、この問題は、次の6命令を順に実行したら最終的にstack[2]の内容はどうなっているか、を問うています。
stack[1]からpopした値をstack[3]にpush
stack[1]からpopした値をstack[3]にpush
stack[1]からpopした値をstack[3]にpush
stack[3]からpopした値をstack[2]にpush
stack[3]からpopした値をstack[2]にpush
stack[3]からpopした値をstack[2]にpush

2025.10.31 00:24

jjon-comさん(No.4)

★FE プラチナマイスター

再帰処理の流れを理解する要点は、
地を這う虫のように一行一行トレースを始めるのではなく、
プログラムの開始から終了までの全体の流れはこうなる、と、
自分自身を呼び出す入れ子の関係の全体像をイメージすることだと考えます。
各命令の実行により変数がどう変化していくかをトレースするのはその後です。

ちなみに。
「地を這う虫のように」というのはトレース作業を揶揄しているのではなく、
鳥瞰図・虫瞰図、という日本語があるからそう形容しただけです。念のため。

2025.10.31 08:44

waaさん(No.5)

詳しくありがとうございました。時間はかかりますが、自分で図を書き、理解できました！！

2025.11.01 15:06

スレッドの先頭へ»

基本情報技術者試験情報＆徹底解説 -新制度に完全対応-

大滝本4.10について [6125]

その他のスレッド