VBA プロシージャ呼び出しの仕組みから再帰を理解する

以前に以下の記事で再帰を説明するのに、普通の関数呼び出しに置き換えるアプローチをとった。
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という操作でデータを取り出すことができる。
f:id:t-hom:20180731035029p:plain

プロシージャを呼び出すと、以下の情報がスタックに積まれる。

呼び出し元のローカル変数
呼び出しが終わったらどこに戻れば良いのか(つまり呼び出し元情報)

今回の例では、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では無理なので、イメージで補って欲しい。

まとめ

再帰は自分自身を呼び出すと聞いて、あれ？途中の変数はどうなるの？と混乱される方が多い。
かくいう私もそうだった。

プロシージャごとにローカルスコープが作られるという理解だと、この混乱を避けることができない。
正しくは、プロシージャの呼び出しごとにスタックによってスコープが作られるのだ。
だからたとえ呼び出し先が自分自身であってもスコープは新しく作られ、呼び出しから戻ればまた元のスコープに戻って、変数の値も元通りという訳だ。
これが再帰の仕組み。