基本情報技術者試験詳しい方へ、回答求む [問題]三つのスタックA, B, Cのいずれの初期状態も[1

基本情報技術者試験詳しい方へ、回答求む

[問題]三つのスタックA, B, Cのいずれの初期状態も[1, 2, 3]であるとき、再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。ここで、スタックが、[a1, a2， …， an-1]の状態のときにanをpushした後のスタックの状態は[a1, a2， …， an-1， an]で表す。

f(){
Aが空ならば {
何もしない。
} そうでない場合 {
Aからpopした値をCにpushする。
f()を呼び出す。
Cからpopした値をBにpushする。
}
}

こう言う問題があるんですけど、
f()を呼び出す。の処理が終わるところ(再帰的呼び出しが終わるところ)までは理解できるんです。
そのあとのCからpopした値をBにpushする。の処理が3回行われるのがなぜかわかりません。
おしえてください、、、

質問者からの補足コメント

• 答え書くの忘れました。 [1，2，3，1，2，3]

    補足日時：2021/04/08 08:54

No.3 ベストアンサー 回答者： spookyaction 回答日時： 2021/04/08 10:13

図にすればこんな感じです。

再帰実行の一番深いところから戻る過程でC→Bが３回実行されるのが見て取れます。

この回答へのお礼

分かりやすく助かりました！ありがとうございました！！

お礼日時：2021/04/08 12:23

No.4 回答者： sukitaro 回答日時： 2021/04/08 10:22

A[1,2,3]

B[1,2,3]
C[1,2,3]

f()が呼び出される（1回目始まり）
A空でないので、Aからpopした値をCにpushする。
A[1,2]
B[1,2,3]
C[1,2,3,3]

f()が呼び出される（2回目始まり）
A空でないので、Aからpopした値をCにpushする。
A[1]
B[1,2,3]
C[1,2,3,3,2]

f()が呼び出される（3回目始まり）
A空でないので、Aからpopした値をCにpushする。
A[]
B[1,2,3]
C[1,2,3,3,2,1]

f()が呼び出される（4回目始まり）
A空なので何もしない。
f()4回目終わり。

f()3回目の続き：Cからpopした値をBにpushする。
A[]
B[1,2,3,1]
C[1,2,3,3,2]
f()3回目終わり。

f()2回目の続き：Cからpopした値をBにpushする。
A[]
B[1,2,3,1,2]
C[1,2,3,3]
f()2回目終わり。

f()1回目の続き：Cからpopした値をBにpushする。
A[]
B[1,2,3,1,2,3]
C[1,2,3]
f()1回目終わり。

この回答へのお礼

ありがとうございました！！

お礼日時：2021/04/08 12:20

No.2 回答者： spookyaction 回答日時： 2021/04/08 09:59

B→C転送ではなくC→B転送の間違いでした。

No.1 回答者： spookyaction 回答日時： 2021/04/08 09:54

最初にf()が呼び出されて、その後Aが空になるまで再帰的にf()が3回呼び出されるが、それぞれ呼び出されるf()の処理をf0, f1, f2, f3と呼ぶとします。

f3ではAは空になっているので何も起きず、単にf2に戻るだけで、そこでB->Cの転送が行われてf2が終わります。その後f1の処理に移り、同様にB->Cの転送が行われf1が終わって、f0に処理が移りまたB->Cの転送が行われ全処理が終了。
つまり、B->Cは３回行われます。