第９講　プロシージャの再帰的使用

第７話　プロシージャの再帰的使用による順列の作成の解説

Public Class Form1
　　 '変数の宣言と初期化
　　 Dim n, s As Integer
　　 Dim a(12) As Integer
　　 Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

　　　　　s = 0
　　　　　'順列次数取得
　　　　　n = TextBox1.Text
　　　　　'データグリッドビューのデータのクリア
　　　　　DataGridView1.Rows.Clear()
　　　　　f(0)
　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　DataGridView1(12, s + 1).Value() = s '総数表示

　　 End Sub

　　 Sub f(ByVal g As Integer)
　　　　　Dim h As Integer

　　　　　For i = 1 To n
　　　　　　　a(g) = i
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
　　　　　Next
　　 End Sub

End Class

の続きをトレースしましょう。３で２の世界のループの最後ですから、入れ子式人形の一番内側の人形f(2)は終了となります。
プロシージャは、呼び出されたときだけ存在し、使命が終了すると消滅します。
生成消滅を繰り返すのです。
呼び出されたときだけメモリ上に存在し、任務を終えるとメモリから消えます。
ですからf(2)は終了と同時に消滅します。
入れ子式人形の比喩も終わりとなります。
なぜなら、入れ子式人形の各人形は消滅はしません。
ですが、自己再帰型の場合終了と同時にもっとも内側の人形が消滅するのです。つまり、

となります。本当はもっと正確に表示すると

です。プロシージャf(2)の消滅は、セル番号２の世界自体の消滅だからです。
初めてPrivate Sub Button1_Clickからf(0)が呼び出されてきたときも正確には、

ではなく、

です。f(0)、f(1)、f(2)は呼び出されたときだけ生まれます。
入れ子式人形の比喩で説明してきましたが、
初めてPrivate Sub Button1_Clickからf(0)が呼び出されてきたときには、人形はf(0)しか存在しません。
つまり、この段階では入れ子式人形になっていないのです。
f(0)がf(1)を呼び出したとき、

初めて入れ子式人形になるのです。
つまり、fがfを呼び出したとき初めて入れ子式人形になるのです。
自分が自分を呼び出したときに、呼び出した自分が外側の人形になり、
呼び出された自分が内側の人形になるのです。
ですから、自己再帰型のプロシージャを比喩的に表す入れ子式人形は、
発生したり、消滅したりを繰り返す奇妙な人形です。

話を戻しましょう。

セル番号１の世界に戻るとFor i = 1 To nによって、セル番号１の世界最後のループ

となります。
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
によって、１と３が比較されますが内容が一致しないので、hの値は１のままで、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
が実行されf(2)が呼び出され、入れ子式人形が再び３重になります。そして、２回目のf(2)の1巡目のループにより、

となり、
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の１巡目において１と１が比較され、内容が同じなのでh=0となります。
したがって、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
はスルーされ、２回目のf(2)の２巡目のループとなり、

　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の１巡目と２巡目においてそれぞれ、１と２、３と２が比較されますがいずれも内容が違いますので、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
が行われます。
ところが、g+1<nは3<3で等しくなく、
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
は実行されず、Else文の方が実行され、順列の２つめがデータグリッドビューに表示されます。
そして、s = s + 1によって順列総数も２をカウントすることになります。
次に、２回目のf(2)の３巡目になり、

　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の２巡目で３と３が比較され、h=0となり、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
は実施されず、２回目のf(2)の消滅となります。

そして、f(1)のループも終わりf(1)が消滅します。

そして、f(0)の２巡目が行われ

g=0から
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
はスルーされ、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
の命令が実施され、f(1)の２回目の発生となります。

２回目のf(1)の１巡目によって

となりますが、２と１は一致しないので
すぐにf(2)がよびだされ、f(2)の4回目の発生となります。

４回目のf(2)の１巡目によって、

となりますが、
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の２巡目の試験をパスせずh=0となり、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
は無視され、４回目のf(2)の２巡目によって

となります。
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の1巡目の検査に抵触して、４回目のf(2)の３巡目

になりますが、
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の1巡目と２巡目を簡単にクリアして、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
が舞台に登場しますが、3<3から前半のIf g + 1 < n Thenは活躍の場がなく、
Else文に主役の座を譲ります。
こうして、データグリッドビューに３個目の順列が表示されカウンタも３となります。
これで４回目のf(2)は４度目の消滅を迎え、

２回目のf(1)の２巡目となりますが、
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の検査をクリアできずあっさり２回目のf(1)の３巡目となり、

今度は
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
をパスして、f(2)の５回目の発生となります。
その１巡目は

　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
をクリアして、４個目の順列がデータグリッドビューに表示されカウンタも４を数えます。
５回目のf(2)の２巡目と３巡目はそれぞれ、

検査
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
を突破できず、f(2)は５度目の消滅を体験します。
続いて、f(1)も２度目の消滅を食らいまして、f(0)の３巡目は、

すぐに
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
を実行して、f(1)を呼び出し、f(1)の３回目の生誕となります。

そして、
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
をクリアして、f(2)の６回目の誕生を迎えます。
その1巡目

は
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
をクリアせず、６回目のf(2)の2巡目となり、

これは
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
のテストをパスして、５個の目の順列がデータグリッドビューに表示されsも５となります。
３巡目

検査
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
に抵触して、f(2)は５回目の消滅を体験することになります。
３回目のf(1)の２巡目

検査
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
に合格して、f(2)が呼び出され、f(2)の６回目の生成となります。
６回目のf(2)の１巡目

　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の検査を通り抜け、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
のElse文によって６個目の順列がデータグリッドビューに表示され順列総数も６となります。
以下、６回目の２巡目、３巡目

いずれも
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
に阻止され、f(2)の６回目の消滅と相成ります。
３回目のf(1)の３巡目

　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の阻まれ、f(1)は３度目の消滅を迎えます。
そして、

f(0)も天寿を全うして、入れ子式人形のすべてが消え去ります。
自分が消え去った代わりに、データグリッドビューには６個の順列と総数６が燦然と輝いています。

fは自分の天命を成就して人生劇場から退場したのです。

以上で、プロシージャの再帰的使用による順列の作成の解説を終了とします。
いよいよ最終講卒業研究と卒業試験です。

第６話へ　最終講第１話へ

VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座

数学研究室に戻る