以前に以下の記事で再帰を説明するのに、普通の関数呼び出しに置き換えるアプローチをとった。
thom.hateblo.jp
今回はそもそものプロシージャ呼び出しの仕組みから説明しようと思う。
例えば以下のコードでProcedureCall1を実行してみる。
Sub ProcedureCall1() a = 1 Debug.Print a Call Proc1 Debug.Print a End Sub Sub Proc1() a = 2 Debug.Print a End Sub
結果は1, 2, 1と表示される。
ProcedureCall1とProc1における変数aは、名前は同じだけれど別物として扱われる。これは経験を積んだプログラマからすると自明のことだ。
しかしなぜ一つのプログラム実行の中で、同じ変数を別物として扱えるのだろうか。
これはプロシージャ呼び出しに、スタックが使われてることと関係がある。
スタックとは一般的には「積み重ね」という意味で、プログラミング用語としては積み重ね構造を模倣したデータ構造を言う。
Pushという操作でデータを積み、Popという操作でデータを取り出すことができる。
プロシージャを呼び出すと、以下の情報がスタックに積まれる。
- 呼び出し元のローカル変数
- 呼び出しが終わったらどこに戻れば良いのか(つまり呼び出し元情報)
今回の例では、ProcedureCall1がProc1を呼び出すとき、ローカル変数aと戻り先情報(ProcedureCall1の4行目に戻れ)がスタックに積まれる。
そしてProc1が終了すると、スタックから戻り先情報を取り出してその位置にジャンプし、ローカル変数aの中身を元に戻す。
ProcedureCall1のaの内容はスタックに保管されているのでProc1でaが加工されても全く影響がない。
これが基本的なプロシージャ呼び出しの仕組み。
ではVBAのGoSub命令を使ってこのプロシージャ呼び出しの仕組みを模倣してみようと思う。
GoSub命令はラベルにジャンプすることができ、Return命令によって元の位置に戻ることができる。
といっても戻り先情報については変数に格納したりできないので、ローカル変数のスタック処理だけやってみる。
まずVBAにスタックは無いので、自分で作るしかない。
クラスモジュールを挿入し、オブジェクト名を「StackObject」とする。
StackObjectのコードは以下のとおり。今回の記事では特にスタックの実装まで理解する必要はないのでコピペでOK。
Private Items() As Variant Private Sub Class_Initialize() ReDim Items(0) End Sub Public Sub Push(ByRef x As Variant) ReDim Preserve Items(UBound(Items) + 1) Items(UBound(Items)) = x End Sub Public Function Pop() As Variant If UBound(Items) > 0 Then Pop = Items(UBound(Items)) ReDim Preserve Items(UBound(Items) - 1) Else Pop = Empty End If End Function
これを使ったプロシージャ呼び出し時のローカル変数スタックを模倣したコードがこちら。
Sub ProcedureCallImitation() Dim stack As StackObject: Set stack = New StackObject a = 1 Debug.Print a 'ローカル変数aをスタックに退避し、クリアする stack.Push a: a = Empty 'プロシージャを呼び出す。 GoSub Proc1 '呼び出しから戻ったらスタックからローカル変数aに戻す a = stack.Pop Debug.Print a Exit Sub Proc1: a = 2 Debug.Print a Return End Sub
上記コードでは実際にはひとつのプロシージャの中で変数aを使いまわしているが、スタックを利用しているのであたかも別プロシージャの別の変数であるかのように扱うことができる。
普通のプロシージャの呼び出しでも、マシン語レベルではこれと同じことが起きている。ただプログラマーがスタックを意識しなくて良いようにVBAを含めた高級言語ではそのあたりが抽象化されているだけ。
次に同じ仕組みでプロシージャの再帰呼び出しをスタックを使ってやってみよう。
まずは普通の再帰コード。
Sub RecursiveProcedureCall() Dim arg As Integer arg = 1 Call RecProc1(arg) End Sub Sub RecProc1(arg) If arg < 5 Then Call RecProc1(arg + 1) End If Debug.Print arg End Sub
実行すると5, 4, 3, 2, 1と表示される。
処理の流れが分かりにくい場合はF8で一行ずつステップ実行すると良い。
これをスタックとGoSubを使って1つのプロシージャで書いたのがこちら。
Sub RecursiveProcedureCallImitation() Dim stack As StackObject: Set stack = New StackObject Dim arg As Integer arg = 1 stack.Push arg GoSub RecProc1 Exit Sub RecProc1: If arg < 5 Then arg = arg + 1 stack.Push arg GoSub RecProc1 End If arg = stack.Pop Debug.Print arg Return End Sub
RecProc1を呼び出しす度にスタックには1, 2, 3, 4 ,5の順でデータがPushされる。
そして呼び出しの最後でスタックからPopされるので出力順は5, 4, 3, 2, 1となる。
このコードは同じ個所を繰り返し呼び出しているが、変数argは都度スタックにPushされているので、あたかもargは呼び出しごとに別のスコープであるかのように扱うことができる。
これも分かりにくければステップ実行してみると良いが、F8だとStackの内部コードにまで入り込んでしまうので、Shift+F8で1行ずつ実行すると良い。
Stack内部に入ってしまった場合は抜けるまでF8を何度か押すか、Ctrl+Shift+F8で抜けられる。
ちなみにGoSubでラベルにジャンプした場合にReturnで呼び出し元に戻ってこられるのも裏でスタックが働いているおかげ。ラベルを変数に入れられたらもっと細かいところまで模倣できたんだけど残念ながらVBAでは無理なので、イメージで補って欲しい。
まとめ
再帰は自分自身を呼び出すと聞いて、あれ？途中の変数はどうなるの？と混乱される方が多い。
かくいう私もそうだった。
プロシージャごとにローカルスコープが作られるという理解だと、この混乱を避けることができない。
正しくは、プロシージャの呼び出しごとにスタックによってスコープが作られるのだ。
だからたとえ呼び出し先が自分自身であってもスコープは新しく作られ、呼び出しから戻ればまた元のスコープに戻って、変数の値も元通りという訳だ。
これが再帰の仕組み。
余談
今回スタックというデータ構造を紹介したが、他にも色々と使い道があるので紹介。
ネストした構造を扱うのにスタックを使う。
thom.hateblo.jp
thom.hateblo.jp
普通は再帰で実装するアルゴリズムをあえてループで実装するにはスタックが必要。
thom.hateblo.jp
あとは記事は書いてないけれど、Undo-Redoの仕組みもスタックだし、ブラウザの戻る-進むもスタックである。
スタックは情報処理分野ではLIFO(Last In First Out)あるいはFILO(First In Last Out)と呼ばれるデータ構造だ。
今後もし直接使うことはなくても、思考の幅を広げてくれる面白いデータ構造なので、覚えておいて損はないと思う。
