「繰り返し」と「再帰」は、両方とも、命令セットを繰り返し実行します:
- 繰り返しは、制御条件が偽になるまで、ループが繰り返し実行されます。
- 再帰は、手続き内の命令が、その手続き自体を繰り返し呼び出すときに実行されます。
「繰り返し」と「再帰」の主な違いは、「繰り返し」は、反復実行する「一連の命令」に適用される処理過程であるのに対して、「再帰」は常に「手続き」に適用される処理過程だということです。
「繰り返し」の定義
「繰り返し」は、反復条件が偽になるまで、一連の命令を繰り返し実行する処理過程です。
「繰り返し」ブロックは、初期化、比較、反復される命令の実行、最後に制御変数の更新、で構成されます。
制御変数が更新されると、再度比較され、反復の条件が偽になるまで、処理過程が繰り返されます。
「繰り返し」ブロックは、
For ループ、
While ループ、...です。
「繰り返し」ブロックは、各サイクルで「変数」を保存するための、実行スタックを使いません。
したがって、繰り返しブロックの実行は、再帰ブロックよりも高速です。
さらに、繰り返しには、繰り返される手続きを呼ぶためのオーバーヘッドがありません。これは実行を再帰よりも高速にします。
制御条件が偽になると、繰り返しが完了します。
整数の階乗を返す繰り返し関数の簡単な例：
'' この反復関数は、階乗関数を繰り返す定義を使って、定義されます:
'' Case (n = 0) : factorial(0) = 1
'' Case (n > 0) : factorial(n) = (1) * ..... * (n - 2) * (n - 1) * (n)
'' 最初の行は、累積変数の初期値を決定します : 'result = 1'
'' 2 行目は、蓄積する命令文の構文を決定します: 'result = result * I'
Function iterativeFactorial (ByVal n As Integer) As Integer
Dim As Integer result = 1 '' 変数の初期化
For I As Integer = 1 To n '' 繰り返しループ
result = result * I '' 反復累積
Next I
Return result
End Function
Dim N As Integer
N = 6
Print Str(N) & "! =" ; iterativeFactorial(6)
Sleep
FreeBASIC では、手続きが、コード内で自分自身を呼び出すことができます。
これは、手続き定義に、それ自体への手続き呼び出しがあることを意味します。
手続きで使われるローカル変数とパラメータのセットは、手続きが呼び出されるたびに新しく作成され、実行スタックの最上部に保存されます。
ただし、手続きがそれ自体を呼び出すときに、その手続きの新しいコピーは作成されません。
再帰的手順は、コードのサイズを大幅に削減したり、メモリ使用量を改善したりするわけではありませんが、繰り返しと比べると、少し改善します。
再帰を終了するには、条件をテストして、再帰呼び出しを行わずに、手続きを強制的に戻す必要があります。
再帰的手続きの定義に、条件のテストがないと、一度呼び出された手続きは、無限に再帰のままになります。
注： 再帰手続きのパラメーターが参照で渡される場合、コード本体で値を変更する必要がある場合は、ローカル変数を使うように注意してください。
整数の階乗を返す、再帰関数の簡単な例：
'' 再帰関数のコードは、階乗関数の再帰定義を使って定義されます:
'' Case (n = 0) : factorial(0) = 1
'' Case (n > 0) : factorial(n) = n * factorial(n-1)
'' 最初の行は、終了条件を決定します: 'If (n = 0) Then Return 1'
'' 2 行目は、関数自体を呼び出す命令文の構文を決定します: 'Return n * factorial(n - 1)'
Function recursiveFactorial (ByVal n As Integer) As Integer
If (n = 0) Then '' 終了条件
Return 1
Else '' 再帰ループ
Return n * recursiveFactorial(n - 1) '' 再帰呼び出し
End If
End Function
Dim N As Integer
N = 6
Print Str(N) & "! =" ; recursiveFactorial(6)
Sleep
この関数を、再帰が末尾再帰になるように変換するのは、非常に簡単です。
これを実現するには、関数に新しいパラメーターを追加する必要があります：累算器として機能する 'result' パラメーターです：
Function tailRecursiveFactorial (ByVal n As Integer, ByVal result As Integer = 1) As Integer
If (n = 0) Then '' end condition
Return result
Else '' recursion loop
Return tailRecursiveFactorial(n - 1, result * n) '' tail recursive call
End If
End Function
Print tailRecursiveFactorial(6)
Sleep
今回は、計算は、実行スタックに文脈を送るときに行われます。
以下は、単純な再帰関数「逆文字列」の、同様の変換手順：
Function recursiveReverse (ByVal s As String) As String
If (s = "") Then '' end condition
Return s
Else '' recursion loop
Return recursiveReverse(Mid(s, 2)) & Left(s, 1) '' recursive call
End If
End Function
Print recursiveReverse("9876543210")
Sleep
Function tailRecursiveReverse (ByVal s As String, ByVal cumul As String = "") As String
If (s = "") Then '' end condition
Return cumul
Else '' recursion loop
Return tailRecursiveReverse(Mid(s, 2), Left(s, 1) & cumul) '' tail recursive call
End If
End Function
Print tailRecursiveReverse("9876543210")
Sleep
注：
"&" 演算子（文字列の連結）は対称演算子ではない（ '(a & b) <> (b & a)', 一方 '(x * y) = (y * x)' ）ため、 実行スタックから文脈を取り出す前ではなく、実行スタックに文脈を送るときに、2つの演算対象の順序を逆にする必要があります。
末尾再帰ではないが最終再帰
再帰呼び出しが、実行されたコードの末尾に配置されると、非末尾再帰手続きが最終になります（実行可能な命令行が、複数の再帰呼び出しの前後にありません）。
例１．組み合わせ係数（二項係数） nCp の計算と、パスカルの三角形の表示：
Function recursiveCombination (ByVal n As UInteger, ByVal p As UInteger) As LongInt
If p = 0 Or p = n Then
Return 1
Else
Return recursiveCombination(n - 1, p) + recursiveCombination(n - 1, p - 1)
End If
End Function
Dim As UInteger n = 10
For I As UInteger = 0 To n
For J As UInteger = 0 To I
Locate , 6 * J + 3 * (n - I) + 3
Print recursiveCombination(I, J);
Next J
Print
Next I
Sleep
例２．円の再帰的描画：
Sub recursiveCircle
(ByVal x
As Integer,
ByVal y
As Integer,
ByVal r
As Integer)
Circle (x, y
), r
If r >
16 Then
recursiveCircle
(x + r /
2, y, r /
2)
recursiveCircle
(x - r /
2, y, r /
2)
recursiveCircle
(x, y + r /
2, r /
2)
recursiveCircle
(x, y - r /
2, r /
2)
End If
End Sub
Screen 16
Locate 2,
2
recursiveCircle
(160,
160,
150)
Sleep
例３．クイックソート・解法：
Dim Shared As UByte t(99)
Sub recursiveQuicksort (ByVal L As Integer, ByVal R As Integer)
Dim As Integer pivot = L, I = L, J = R
Do
If t(I) >= t(J) Then
Swap t(I), t(J)
pivot = L + R - pivot
End If
If pivot = L Then
J = J - 1
Else
I = I + 1
End If
Loop Until I = J
If L < I - 1 Then
recursiveQuicksort(L, I - 1)
End If
If R > J + 1 Then
recursiveQuicksort(J + 1, R)
End If
End Sub
Randomize
For I As Integer = LBound(t) To UBound(t)
t(i) = Int(Rnd * 256)
Next I
Print "元の数列:"
For K As Integer = LBound(t) To UBound(t)
Print Using "####"; t(K);
Next K
Print
recursiveQuicksort(LBound(t), UBound(t))
Print "昇順数列:"
For K As Integer = LBound(t) To UBound(t)
Print Using "####"; t(K);
Next K
Print
Sleep
再帰呼び出しが、実行されたコードの最後（少なくとも実行可能な命令行が、いくつかの再帰呼び出しの後またはその間にある）に配置されていない場合、末尾再帰手続きでなく、また最終再帰でもありません。
例、ハノイの塔解法：
'' この例では、2 つの再帰呼び出しは、実行コードブロックの最後にあります。
'' しかし、命令行で区切られており、順序制約があります。
Sub recursiveHanoi (ByVal n As Integer, ByVal departure As String, ByVal middle As String, ByVal arrival As String)
If n > 0 Then
recursiveHanoi(n - 1, departure, arrival, middle)
Print " move one disk from " & departure & " to " & arrival
recursiveHanoi(n -1 , middle, departure, arrival)
End If
End Sub
recursiveHanoi(3, "A", "B", "C")
Sleep
最初の関数が2番目の関数を呼び出し、次に2番目の関数が最初の関数を呼び出す場合、2つの関数は相互に再帰的である、と言われます。
相互再帰を使った例：再帰関数 'even()' 、'odd()' ：
Declare Function recursiveIsEven(ByVal n As Integer) As Boolean
Declare Function recursiveIsOdd(ByVal n As Integer) As Boolean
Function recursiveIsEven(ByVal n As Integer) As Boolean
If n = 0 Then
Return True
Else
Return recursiveIsOdd(n - 1)
End If
End Function
Function recursiveIsOdd(ByVal n As Integer) As Boolean
If n = 0 Then
Return False
Else
Return recursiveIsEven(n - 1)
End If
End Function
Print recursiveIsEven(16), recursiveIsOdd(16)
Print recursiveIsEven(17), recursiveIsOdd(17)
Sleep
再帰関数が、関数に渡された引数が関数自体を参照している場合、入れ子になっている、と言います。
入れ子になった再帰関数を使う例、'Ackermann()' 再帰関数：
Function recursiveAckermann (ByVal m As Integer, ByVal n As Integer) As Integer
If m = 0 Then
Return n + 1
Else
If n = 0 Then
Return recursiveAckermann(m - 1, 1)
Else
Return recursiveAckermann(m - 1, recursiveAckermann(m, n - 1))
End If
End If
End Function
Print recursiveAckermann(3, 0), recursiveAckermann(3, 1), recursiveAckermann(3, 2), recursiveAckermann(3, 3), recursiveAckermann(3, 4)
Sleep
