第１話 再帰的呼び出しとは？
再帰的呼び出しの話に入る前に、
順列の作成を考えてみましょう。
話を簡単にするために１から３の順列を作成する場合を考えてみましょう。
この順列は
| １ | ２ | ３ |
| １ | ３ | ２ |
| ２ | １ | ３ |
| ２ | ３ | １ |
| ３ | １ | ２ |
| ３ | ２ | １ |
の６個です。
これをパソコンに作らせるプログラム例は
３次順列作成
です。
そのプログラムソースは、次のようになっています。
Private Sub CommandButton1_Click()
Dim i As Integer, j As Integer, k As Integer, l As Integer, h1 As Integer,
h2 As Integer, jyn(3) As Integer
Dim sousuu As Long
For i = 1 To 3
jyn(1) = i
For j = 1 To 3
jyn(2) = j
h1 = 1
For k = 1 To 1
If jyn(2) = jyn(k) Then
h1 = 0
Exit For
End If
Next
If h1 = 1 Then
For k = 1 To 3
jyn(3) = k
h2 = 1
For l = 1 To 2
If jyn(3) = jyn(l) Then
h2 = 0
Exit For
End If
Next
If h2 = 1 Then
sousuua = sousuu Mod 8
sousuus = Int(sousuu / 8)
sousuu = sousuu + 1
For l = 1 To 3
Cells(5 + sousuus * 2, 1 + l + sousuua * 4)
= jyn(l)
Next
End If
Next
End If
Next
Next
End Sub
このプログラムには無駄があります。
似たようなことを繰り返しているからです。
ピンクのところと赤の記述がそっくりであることがわかると思います。
さらに言えば、濃い青のところも見かけは少し違うのですが本質は同じです。
というのは、例えば
For l = 1 To 2
If jyn(3) = jyn(l) Then
h2 = 0
Exit For
End If
Next
で行っていることはjyn(3)に入っている数字が
jyn(1)、jyn(2)に入っている数字と重複していないか調べているわけです。
順列は同じ数字を使ってはいけないからです。
濃い青ではたまたま前のマスがないので、調べていないだけです。
ですから、
For i = 1 To 3
jyn(1) = i
の部分は
For i = 1 To 3
jyn(1) = i
h0 = 1
for j = 0 to 0
if jyn(1) = jyn(j) then
h0 = 0
exit for
end if
next
if h0 = 1 then
などとしてもよいわけです。
このように考えると、
濃い青、ピンク、赤で行っていることは本質的には同じことの繰り返しです。
| １ | ２ | ３ |
これは各マスが本質的に同じ構造を持っているからです。
各マスは１から３までの数字が入り、
そのマスの以前のマスと数字が重複しないという共通のルールがあるからです。
同じ構造が繰り返されるときは、
ループ文を使うより再帰的呼び出しを使う方が便利です。
次のプログラム例をクリックしましょう。
再帰的呼び出しによる３次順列の作成
これのプログラムソースは以下のようになっています。
Dim jyn(3) As Integer
Dim sousuu As Long
Private Sub CommandButton1_Click()
sousuu = 0
jyunretusakusei (1)
End Sub
Sub jyunretusakusei(g As Integer)
Dim i, j, h As Integer
For i = 1 To 3
jyn(g) = i
h = 1
If g > 1 Then
For j = 1 To g - 1
If jyn(g) = jyn(j) Then
h = 0
Exit For
End If
Next
End If
If h = 1 Then
If g < 3 Then
jyunretusakusei (g + 1)
Else
sousuua = sousuu Mod 8
sousuus = Int(sousuu / 8)
sousuu = sousuu + 1
For j = 1 To 3
Cells(5 + sousuus * 2, 1 + j + sousuua * 4) = jyn(j)
Next
End If
End If
Next
End Sub
まず、メインプログラムからjyunretusakusei (1)でＳｕｂプロシージャjynretusakuseiを呼び出しています。
さらに、注目はＳｕｂプロシージャjynretusakuseiの中の記述です。
jyunretusakusei (g + 1)で自分自身を呼び出しています。
このように自分で自分を呼び出すことを再帰的呼び出しというのです。
この再帰的呼び出しのメリットは何でしょうか。
大分このファイルも大きくなったのでその点については次話で考えてみたいと思います。
また、今日の話はわからなかった方が多いと思います。
再帰的呼び出しは難解だからです。次話以降で
sousuua = sousuu Mod 8
sousuus = Int(sousuu / 8)
sousuu = sousuu + 1
For j = 1 To 3
Cells(5 + sousuus * 2, 1 + j + sousuua * 4) = jyn(j)
next
や
For l = 1 To 2
If jyn(3) = jyn(l) Then
h2 = 0
Exit For
End If
Next
などの部分も含めて解説していきたいと思います。
