再帰呼び出しでスタックの値はどの順に移るか
基本情報技術者試験 平成31年度春期 午前 問6 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
三つのスタックA，B，Cのいずれの初期状態も[1，2，3]であるとき，再帰的に定義された関数ƒ()を呼び出して終了した後のBの状態はどれか。ここで，スタックが，[ ，…，]の状態のときにをpushした後のスタックの状態は[ ，…，，]で表す。 ƒ(){ Aが空ならば{ 何もしない。 } そうでない場合{ Aからpopした値をCにpushする。 ƒ()を呼び出す。 Cからpopした値をBにpushする。 } }
- ア
[1，2，3，1，2，3]
- イ
[1，2，3，3，2，1]
- ウ
[3，2，1，1，2，3]
- エ
[3，2，1，3，2，1]
会話形式の解説
講師この問題は、Aから取り出す順番と、Bに積む順番を分けて追うのがポイントです。
受験者Aの右端から3、2、1を取り出すので、Bにもその順で入ると思いました。
講師CからBへ移す処理は、再帰呼び出しの前と後のどちらにありますか。
受験者後です。まずAが空になるまで呼び出しが続きます。
講師そうです。その間、Aから取り出した3、2、1をCに積みます。
受験者Aが空になって戻るときは、Cの右端にある1から取り出すのですか。
講師はい。戻る順にCから1、2、3を取り出し、Bに積みます。
受験者Bは初めから[1,2,3]なので、終了時は[1,2,3,1,2,3]ですね。
講師その通りです。後ろに3、2、1が続く候補は、Bへの追加順を逆に考えています。
受験者先頭が[3,2,1]の二つの候補は、Bの初期状態とも違います。
講師はい。Bの既存の値は取り出さないので、先頭の[1,2,3]は残ります。両方とも[3,2,1]の候補は、追加順も違います。
受験者Cも初めから[1,2,3]ですが、その値はBに移らないのですね。
講師AからCに積んだ値を戻る途中ですべて取り出すため、Cの初期要素は残ります。再帰呼び出しより後の処理は、深い呼び出しから戻る順に追うと分かりやすいです。
まとめ
Aからは右端の3、2、1を順に取り出し、Cに積みます。再帰呼び出しから戻るとき、CからBへ移る順番は1、2、3です。Bの初期状態[1,2,3]は変わらないので、終了時のBは[1,2,3,1,2,3]となり、正解はアです。Cの初期要素はBへ移りません。
解答・解説
正解はアです
この問題のテーマ
再帰呼び出しでスタック間の値が移る順序と、処理後のBの状態を問う問題です。
解き方の考え方
スタックでは右端の値をpopします。Aからは3、2、1の順に取り出してCに積み、そのたびに次のƒ()を呼び出します。Aが空になると呼び出し元へ順に戻り、各回でCからBへの移動が行われます。
選択肢ごとの解説
- ○ア [1，2，3，1，2，3]CからBへ移る値は1、2、3の順です。Bの初期状態[1,2,3]の右側にこの順で追加するので、終了時は[1,2,3,1,2,3]になります。
- ×イ [1，2，3，3，2，1]この並びは、Bに3、2、1の順で追加した場合の状態です。実際には再帰呼び出しから戻るときに1、2、3の順で追加します。
- ×ウ [3，2，1，1，2，3]先頭の[3,2,1]がBの初期状態と一致しません。この関数はBの既存の値を取り出さないため、最初の[1,2,3]はそのまま残ります。
- ×エ [3，2，1，3，2，1]Bの初期部分を[3,2,1]としている点が違います。また、Bへの追加部分も[3,2,1]ですが、実際の追加順は1、2、3です。
補足
Cにも最初から[1,2,3]が入っていますが、Aから積んだ値を戻る途中ですべて取り出すため、Cの初期要素はBへ移りません。
POINT
- この表記のスタックでは、右端の値が次にpopされます。
- 再帰呼び出しより前の処理は、深い呼び出しへ進むたびに実行されます。
- 再帰呼び出しより後の処理は、深い呼び出しから戻る順に実行されます。