第２話 再帰的呼び出し型のメリット
メリットは次の２つを見れば一目瞭然です。
７次順列をループ文で作った場合と
再帰的呼び出しで作った場合です。
７次順列ループ方式
７次順列再帰的呼び出し方式
７次順列ループ方式のプログラムソース
Private Sub CommandButton1_Click()
Dim i As Integer, j As Integer, k As Integer, l As Integer, h1 As Integer,
h2 As Integer, h3 As Integer, h4 As Integer, h5 As Integer, h6 As Integer,
jyn(7) As Integer
Dim sousuu As Long
sousuu = 0
For i = 1 To 7
jyn(1) = i
For j = 1 To 7
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 7
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
For l = 1 To 7
jyn(4) = l
h3 = 1
For m = 1 To 3
If jyn(4) = jyn(m) Then
h3 = 0
Exit For
End If
Next
If h3 = 1 Then
For m = 1 To 7
jyn(5) = m
h4 = 1
For n = 1 To 4
If jyn(5) = jyn(n) Then
h4 = 0
Exit For
End If
Next
If h4 = 1 Then
For n = 1 To 7
jyn(6) = n
h5 = 1
For o = 1 To 5
If jyn(6) = jyn(o)
Then
h5 = 0
Exit For
End If
Next
If h5 = 1 Then
For o = 1 To 7
jyn(7) = o
h6 = 1
For p = 1 To 6
If jyn(7) = jyn(p)
Then
h6 = 0
Exit For
End If
Next
If h6 = 1 Then
sousuua = sousuu
Mod 8
sousuus = Int(sousuu
/ 8)
sousuu = sousuu
+ 1
For p = 1 To 7
Cells(5 + sousuus
* 2, 1 + p + sousuua * 8) = jyn(p)
Next
End If
Next
End If
Next
End If
Next
End If
Next
End If
Next
End If
Next
Next
End Sub
７次元ループになっていて、
同じような記述が永遠と繰り返されています。
繰り返しはコンピュータの得意技であって、
人間がやるべきではありません。
ところが、再帰的呼び出しにすると、
Dim jyn(7) As Integer
Dim sousuu As Long
Private Sub CommandButton1_Click()
sousuu = 0
jyunretusakusei (1)
End Sub
Sub jyunretusakusei(g As Integer)
Dim i As Integer, j As Integer, h As Integer
For i = 1 To 7
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 < 7 Then
jyunretusakusei (g + 1)
Else
sousuua = sousuu Mod 8
sousuus = Int(sousuu / 8)
sousuu = sousuu + 1
For j = 1 To 7
Cells(5 + sousuus * 2, 1 + j + sousuua * 8) = jyn(j)
Next
End If
End If
Next
End Sub
とシンプルになっています。さらに、注目点は３次の場合との比較です。
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 As Integer, j As Integer, 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
要するに３次の場合の３を７（４は３＋１、８は７＋１と考えてください。）に変更するでだけでよいのです。
７次でさえこれだけ違います。
これが２０次ぐらいになったら再帰的呼び出しが如何に便利かわかるでしょう。
プログラムはまだ改良の余地があります。
３や７を例えばnとしておくべきです。
こうしておけば、メインの一番最初でn＝７と一カ所だけ変更すればよいのです。
さらに、次の例のようにしておけばプログラムソースをいじらなくてすみます。
Dim jyn(12), n As Integer
Dim sousuu As Long
Private Sub CommandButton1_Click()
n = Cells(2, 11)
sousuu = 0
jyunretusakusei (1)
End Sub
Sub jyunretusakusei(g As Integer)
Dim i As Integer, j As Integer, h As Integer
For i = 1 To n
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 < n Then
jyunretusakusei (g + 1)
Else
sousuua = sousuu Mod 20
sousuus = Int(sousuu / 20)
sousuu = sousuu + 1
If sousuu = 1 Then
Range("m3:o3").Select
With Selection
.HorizontalAlignment = xlGeneral
.VerticalAlignment = xlCenter
.WrapText = False
.Orientation = 0
.AddIndent = False
.IndentLevel = 0
.ShrinkToFit = False
.ReadingOrder = xlContext
.MergeCells = True
End With
Cells(3, 10) = "順列総数"
Cells(2, 1).Select
End If
Cells(3, 13) = sousuu
For j = 1 To n
Cells(5 + sousuus * 2, 1 + j + sousuua * (n + 1)) =
jyn(j)
Next
End If
End If
Next
End Sub
n = Cells(2, 11)でエクセルのＫ２の数字がnに代入されています。
このように共通な数字は、
具体的な数字で書かないで文字で表すのがこつです。
n = Cells(2, 11)としておけば、いちいちプログラムソースをいじらないですむのです。
Ｋ２に１から１２までの数字を入力して実行ボタンを押せば、
１次から１２次までの順列ができます。
１２を上限にしている理由は、このぐらいになると処理時間が長くなってしまうからです。
理論的には２０でも３０でもかまわないわけです。
さて、再帰的呼び出しのメリットがわかったかと思います。
私の魔方陣プログラムでは、再帰的方法をあちらこちらで使用しています。
プログラムによって１００万次元ループも扱っています。
ループ文ではとても書ききれないものが、
再帰的呼び出しでは簡単にできてしまうのです。
上のプログラム例では少し、部品が大きすぎるようです。
例えば、表示の部分を独立させると次のプログラムになります。
ｎ次順列再帰的呼び出し改良例
プログラム内容の解説は、次話以降で行います。
第１話へ 第３話へ
