基本情報技術者試験より 〜スタックを操作する再帰処理をPythonで再現〜
突然ですが、再帰処理って難しくないですか？
今回は基本情報技術者試験の勉強をしていて、問題の解説を読んでもいまいち腹落ちできず、本当にそう動くのかをPythonで記載して検証してみましたのでご報告します。
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する。
}
}
2.答えと解説
A・B・C3つのスタックがあり、問題に記載された関数fを実行すると、Bのスタックは [1, 2, 3, 1, 2, 3] となります。
（Aは[]（空）、Cは[1, 2, 3]）
スタックは「後入後出し（Last In First Out）」なので、AからCに「3 → 2 → 1」の順に渡されて、CからBには「1 → 2 → 3」の順で渡されるので、答えが[1, 2, 3, 1, 2, 3] となること自体はOKです。
文句はありません。
ところが解説を読んでみると・・・
＜プログラム開始＞
A[1，2，3] B[1，2，3] C[1，2，3]
〔f() 呼び出し1回目〕
Aからpopした値をCにpushする。Aから一番右の"3"が取り出され、Cの一番右に追加される(以下、取出位置と追加位置は同様)。
A[1，2] B[1，2，3] C[1，2，3，3]
〔f() 呼び出し2回目〕
Aからpopした"2"をCにpushする。
A[1] B[1，2，3] C[1，2，3，3，2]
〔f() 呼び出し3回目〕
Aからpopした"1"をCにpushする。
A[] B[1，2，3] C[1，2，3，3，2，1]
〔f() 呼び出し4回目〕
Aが空なので何もしない
〔f() 呼び出し3回目の続き〕
Cからpopした"1"をBにpushする。
A[] B[1，2，3，1] C[1，2，3，3，2]
//f() 3回目終了
〔f() 呼び出し2回目の続き〕
Cからpopした"2"をBにpushする。
A[] B[1，2，3，1，2] C[1，2，3，3]
//f() 2回目終了
〔f() 呼び出し1回目の続き〕
Cからpopした"3"をBにpushする。
A[] B[1，2，3，1，2，3] C[1，2，3]
//f() 1回目終了
＜プログラム終了＞
関数f()が終了した後のBの状態は[1，2，3，1，2，3]になっています。したがって「ア」が正解です。
問題の関数ですが、Aのスタックが空でないとき、Aの値をCに格納（Push）する。その後、関数内で再度同じ関数を呼び出し、Cの値をBに格納（Push）します。
再度呼び出された関数もまず、Aのスタックが空でなければ、Aの値をCにPushして、また関数を呼び出し、Cの値をBに格納します・・・
なんかこんがらがってきませんか？
並び順に異論はないものの、処理の流れが頭の中だとイメージできない。
解説を読んで、一瞬分かった気になるものの、やっぱり腑に落ちない・・・
そこでPythonでコードを実際に書いて動かしてみます。
3.Pythonで問題の関数と配列A・B・Cを用意して実行してみる
以下のように作成します。
#pop_push関数を定義する(a,b,cに配列を、nは何回目の処理かをカウントする変数）
def pop_push(a, b, c, n):
#配列aが空なら、Aは空と出力する
if len(a) == 0:
print('Aは空')
pass
#配列Aがからでない場合の処理を記載
else:
#カウント変数nをカウントアップする
n += 1
print("---------------------------------")
#処理結果を出力する（何回目の呼び出しか）
print('{}回目の呼び出し'.format(n))
#配列aの最後尾の値を、配列cに追加し、aから削除
c.append(a[-1])
a.pop(-1)
＃配列aとcの内容を出力する
print('リストaの状態:{}'.format(a))
print('リストcの状態:{}'.format(c))
print("---------------------------------")
#再度関数pop_pushを呼び出す
pop_push(a, b, c, n)
print("---------------------------------")
#呼び出し回数と各配列の内容を出力する
print('{}回目の呼び出し'.format(n))
print('リストaの状態:{}'.format(a))
print('リストbの状態:{}'.format(b))
print('リストcの状態:{}'.format(c))
print("---------------------------------")
#配列bに配列cの最後尾の値を追加し、配列cからは削除する
b.append(b[-1])
c.pop(-1)
#処理結果として、配列a, b, cを返す
return a, b, c
#配列a, b, cを定義する
a = [1,2,3]
b = [1,2,3]
c = [1,2,3]
#result変数に処理結果を返すよう、関数pop_pushに配列a, b, cとカウント変数０を渡す
result = pop_push(a, b, c, 0)
#resultに返ってきた処理結果を出力する
print("---------------------------------")
print("結果：{}".format(result))
print("---------------------------------")4.処理経過と結果を確認する
プログラムを実行すると・・・
---------------------------------
1回目の呼び出し
リストaの状態:[1, 2]
リストbの状態:[1, 2, 3, 3]
---------------------------------
---------------------------------
2回目の呼び出し
リストaの状態:[1]
リストbの状態:[1, 2, 3, 3, 2]
---------------------------------
---------------------------------
3回目の呼び出し
リストaの状態:[]
リストbの状態:[1, 2, 3, 3, 2, 1]
---------------------------------
Aは空
---------------------------------
3回目の呼び出し
リストaの状態:[]
リストbの状態:[1, 2, 3]
リストcの状態:[1, 2, 3, 3, 2, 1]
---------------------------------
---------------------------------
2回目の呼び出し
リストaの状態:[]
リストbの状態:[1, 2, 3, 1]
リストcの状態:[1, 2, 3, 3, 2]
---------------------------------
---------------------------------
1回目の呼び出し
リストaの状態:[]
リストbの状態:[1, 2, 3, 1, 2]
リストcの状態:[1, 2, 3, 3]
---------------------------------
---------------------------------
結果：([], [1, 2, 3, 1, 2, 3], [1, 2, 3])
---------------------------------まさに解説の通り、Aが空になるまで関数を再度呼び出しながら配列aの値をcにPushし続け、Aが空になると今度は3回目・2回目・1回目の処理の続きとして配列cの値をbにPushし続けてますね。
ただ、僕だけかもしれないですが、やっぱり完全に理解しきれないです。
なので、もし同様の処理をするとしたら、自分なら以下のように書くと思います。
def pop_push(a, b, c):
while len(a) > 0:
c.append(a[-1])
a.pop(-1)
while len(c) > 3:
b.append(c[-1])
c.pop(-1)
return a, b, c
a = [1, 2, 3]
b = [1, 2, 3]
c = [1, 2, 3]
result = pop_push(a, b, c)
print(result)出力結果は、以下のように同一となります。
([], [1, 2, 3, 1, 2, 3], [1, 2, 3])頭がいい人ならできるのかもしれないですが、再帰関数を利用するのは難しいのではないかと思います。（なんか予想外の動きをして思い通りになれなそう・・・）
以上