あらゆる
再帰を単純な
繰返しに
置き換える方法、あるいは無制限の
繰返しを独自のスタックに置き換える方法。
序文:
繰返しと再帰は、特にあるスクリプトを一定回数実行することで、コードの最適化を可能にする、プログラムを組む上で非常に便利な 2つの方法です。繰返しは比較的容易に理解できるものですが、再帰は必ずしも最初から明白にならない概念です。
再帰的な手続き(サブルーチンや関数)について語るとき、私たちは構文上の特徴を参照します。
しかし、線形またはツリーの再帰的なプロセスについて話すとき、私たちは手続きの記述の構文ではなくプロセスの流れに興味があります。
したがって、手続きは再帰的な定義を持つことができますが、繰返しプロセスに対応しています。
いくつかの処理は、自然に再帰アルゴリズムとして実装されます(ただし、これは常に最適なソリューションとは限りません)。
再帰的アプローチの主な問題点は、実行スタック上に多くのスペースを消費する可能性があることです。再帰の「深さ」があるレベルに達すると、スレッドの実行スタックに割り当てられたスペースを使い果たし、「スタックオーバーフロー」タイプのエラーが発生します。
また、同じ手続きを繰り返し呼び出すことで、コードが簡単になることもありますが、実行速度は遅くなります。
実行速度を上げるには、単純な再帰的アルゴリズムを、より複雑なループを使った繰返し的アルゴリズムに作り変えると、実行速度が格段に上がります。
繰返し型のソリューションと比べて実行時間やメモリ容量が増えるのであれば、再帰の意味はあるのでしょうか?
繰返しを変換する方法が存在しない場合や、存在しても実装が非常に重い(例えば、実行スタックの代わりに動的な記憶容量が必要)など、繰返し以外の方法では実現できない場合があります。
目次
1. 再帰と繰返しの定義
再帰と繰返しは、どちらも命令セットを繰り返し実行するものです:
- 再帰は、手続き内の命令がその手続き自体を繰り返し呼び出すときに発生します。
- 繰返しは、制御条件が偽になるまでループが繰り返し実行されるときに発生します。
再帰と繰返しの大きな違いは、再帰は常に手続きに適用される処理であるのに対し、繰返しは繰り返し実行する一連の命令に適用されることです。
再帰の定義
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 '' end condition
Return 1
Else '' recursion loop
Return n * recursiveFactorial(n - 1) '' recursive call
End If
End Function
繰返しの定義
繰返しとは、繰返し条件が偽になるまで、一連の命令を繰り返し実行する処理のことです。
繰返しブロックには、初期化、比較、繰返される命令の実行、そして最後に制御変数の更新が含まれます。
制御変数が更新されると、再び比較が行われ、繰返しの条件が偽になるまで処理が繰り返されます。
繰返しブロックは、"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 '' variable initialization
For I As Integer = 1 To n '' iteration loop
result = result * I '' iterative accumulation
Next I
Return result
End Function
2. 再帰を繰返しに置き換える場合の問題点
解決すべき問題が何であれ、繰返し手続きの記述と再帰手続きの記述のどちらかを選択する必要があります。
問題が自然な再帰的構造を持っている場合、再帰的プログラムは選択された構造の単純な適応です。例えば、上で紹介した階乗関数などがそうです。
ただし、再帰的なアプローチには欠点があります:いくつかの言語は再帰を認めていませんし(機械語のように!)、再帰的な手続きは実行時間だけでなくメモリ(実行スタック)にも負担がかかります。
これらの欠点は、再帰的な手続きを一行ごとに繰返し的な手続きに変換することで克服できます。
再帰を繰返しに置き換えることで、利用可能な実行スタックサイズによるサイクル数の制限を抑えることができます。
ただし、独自のストレージ・スタックを使う繰返しでは、スタックデータを押したり引いたりする手続きの呼び出しにかかる時間は、一般的に各呼び出しサイクルで再帰手続きのパラメータを渡す時間よりも大きくなります。
このような変換によって得られる繰返し手続きの複雑さは、再帰手続きの構造によって異なります:
- ある種の再帰的手続き(下記の末尾再帰を参照)では、再帰的手続きのパラメータ(渡された引数)に対応するローカル変数を定義するだけで、非常に簡単に繰返し手続きに変換できます。
- 他の形式の再帰手続き(非末尾再帰)とは逆に、再帰呼び出しと同様に、文脈を保存するために、繰返し手続きでユーザー・ストレージ・スタックを使う必要があります(各呼び出しで渡された引数の値):
- 再帰的な手続きを実行するとき、各再帰呼び出しは実行スタックに文脈をプッシュします。
- 再帰の停止条件が発生すると、実行スタックから別の文脈が次々にポップされ、手続きの実行が継続されます。
3. 末尾再帰を単純な繰返しに置き換える
唯一の再帰呼び出しが再帰の最後にあり、従って他の命令文が後ろに続かない場合、再帰手続きは、末尾再帰手続きとなります:
- 再帰的サブルーチンの場合、唯一の再帰呼び出しは再帰の最後にあります。
- 再帰関数の場合、再帰呼び出しは再帰の最後だけで、他の追加操作を行わないで関数の戻りを考慮することで構成されます。
末尾再帰手続きは、簡単に繰返し手続きに変換できます。
その原理は、再帰呼び出しが手続きの最後の命令である場合、実行スタックに戻る必要がないため、現在の呼び出しの文脈を実行スタックに残しておく必要はありません:
- パラメータを新しい値に置き換えて、手続きの先頭から実行を再開すればよいのです。
- このようにして再帰は繰返しに変換され、実行スタックのオーバーフローを引き起こす危険はなくなります。
非末尾再帰的手続きの中には、末尾再帰的手続きに変換できるものがあります。場合によっては、もう少し複雑なコードになることもありますが、その後、反復的手続きに変換される前であっても、末尾再帰的手続きは多くの場合、メモリ使用量と実行時間が増加していることがあります。
単純な「階乗」再帰関数の例:
非末尾再帰形式(すでに上記で示されています):
Function recursiveFactorial (ByVal n As Integer) As Integer
If (n = 0) Then '' end condition
Return 1
Else '' recursion loop
Return n * recursiveFactorial(n - 1) '' recursive call
End If
End Function
この関数は、再帰呼び出しが関数の最後にあるにもかかわらず、この再帰呼び出しは関数の最後の命令ではないため、非末尾再帰形式となっています。なぜならば、
recursiveFactorial(n - 1) が得られたときには、再び
n を掛ける必要があるからです。
この計算は、実行スタックから文脈をポップするときに行われます。
この関数を、再帰が末尾再帰になるように変換するのは非常に簡単です。
そのためには、関数に新しいパラメータを追加する必要があります:それは、累算器として機能する
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
今回は、実行スタックに文脈をプッシュするときに計算しています。
末尾の再帰は、再帰呼び出しの直前に
n - 1 と
result * n を計算することで、より明確になります:
Function explicitTailRecursiveFactorial (ByVal n As Integer, ByVal result As Integer = 1) As Integer
If (n = 0) Then '' end condition
Return result
Else '' recursion loop
result = result * n
n = n - 1
Return explicitTailRecursiveFactorial(n, result) '' tail recursive call
End If
End Function
ここで、繰返し関数を得るためには、関数呼び出しの代わりに
Goto begin で手続きの先頭から実行を再開します:
Function translationToIterativeFactorial (ByVal n As Integer, ByVal result As Integer = 1) As Integer
begin:
If (n = 0) Then '' end condition
Return result
Else '' iteration loop
result = result * n '' iterative accumulation
n = n - 1
Goto begin '' iterative jump
End If
End Function
最後に、
If ... Goto ... End If 命令は避けた方が良いでしょう。代わりに、例えば
While ... Wend ブロックを使えます。
While ... Wend ブロックを使うことで、追加された
result パラメータをローカル変数に変換できます:
Function betterTranslationToIterativeFactorial (ByVal n As Integer) As Integer
Dim As Integer result = 1
While Not (n = 0) '' end condition of iterative loop
result = result * n '' iterative accumulation
n = n - 1
Wend
Return result
End Function
以下は、同様の変換手順の単純な「逆文字列」再帰関数:
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
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
注意:
演算子
& (文字列の連結)は対称演算子ではない(
(a & b) <> (b & a), 一方、前述のように
(x * y) = (y * x))ため、実行スタックから文脈をポップする前ではなく、実行スタックに文脈をプッシュするときに、2つの演算対象の順序を逆にしなければなりません。
Function explicitTailRecursiveReverse (ByVal s As String, ByVal cumul As String = "") As String
If (s = "") Then '' end condition
Return cumul
Else '' recursion loop
cumul = Left(s, 1) & cumul
s = Mid(s, 2)
Return explicitTailRecursiveReverse(s, cumul) '' tail recursive call
End If
End Function
Function translationToIterativeReverse (ByVal s As String, ByVal cumul As String = "") As String
begin:
If (s = "") Then '' end condition
Return cumul
Else '' iteration loop
cumul = Left(s, 1) & cumul '' iterative accumulation
s = Mid(s, 2)
Goto begin '' iterative jump
End If
End Function
Function betterTranslationToIterativeReverse (ByVal s As String) As String
Dim As String cumul = ""
While Not (s = "") '' end condition of iterative loop
cumul = Left(s, 1) & cumul '' iterative accumulation
s = Mid(s, 2)
Wend
Return cumul
End Function
あまり単純ではない例、非末尾再帰関数「フィボナッチ数列」:
末尾再帰関数への変換があまり明白でない場合もあります。
再帰関数のコード本体は、フィボナッチ数列の再帰的定義を用いて定義されます:
Case (n = 0) : F(0) = 0
Case (n = 1) : F(1) = 1
Case (n > 1) : F(n) = F(n-1) + F(n-2)
最初の2行で終了条件を決定しています:
If n = 0 Or n = 1 Then Return n
3行目で、関数自体を呼び出す命令文の構文を決定します:
Return F(n - 1) + F(n - 2)
非末尾再帰形式のコード:
Function recursiveFibonacci (ByVal n As UInteger) As LongInt
If n = 0 Or n = 1 Then '' end condition
Return n
Else '' recursion loop
Return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2) '' recursive call
End If
End Function
最大値での実行時間はもはや無視できないものになっています。
実際、F(n) を計算するためには、2^(n-1) 回の呼び出しがあり、n=31 では約100万回になります.
再帰アルゴリズムを線形にするために、数列の前の値と最後の値に対応する 2つのパラメータを持つ再帰関数を用いて、 f(n, a, b) とします。
次のようになります:
Case (n = 1): a = F(0) = 0, b = F(1) = 1
Case (n-1): a = F(n-2), b = F(n-1)
Case (n): F(n-1) = b, F(n) = F(n-1) + F(n-2) = a + b
この結果、この新しい関数 f(n, a, b) では、再帰呼び出しは f(n-1, b, a+b) となり、呼び出し回数は (n-1) 回だけになります。
末尾再帰形式のコード:
Function tailRecursiveFibonacci (ByVal n As UInteger, ByVal a As UInteger = 0, ByVal b As UInteger = 1) As LongInt
If n <= 1 Then '' end condition
Return b * n
Else '' recursion loop
Return tailRecursiveFibonacci(n - 1, b, a + b) '' tail recursive call
End If
End Function
そして、先ほどと同様の変換を行い、繰返し形式を求めます:
Function explicitTailRecursiveFibonacci (ByVal n As UInteger, ByVal a As UInteger = 0, ByVal b As UInteger = 1) As LongInt
If n <= 1 Then '' end condition
Return b * n
Else '' recursion loop
n = n - 1
Swap a, b
b = b + a
Return explicitTailRecursiveFibonacci(n, a, b) '' tail recursive call
End If
End Function
Function translationToIterativeFibonacci (ByVal n As UInteger, ByVal a As UInteger = 0, ByVal b As UInteger = 1) As LongInt
begin:
If n <= 1 Then '' end condition
Return b * n
Else '' iteration loopp
n = n - 1
Swap a, b
b = b + a
Goto begin '' iterative jump
End If
End Function
Function betterTranslationToIterativeFibonacci (ByVal n As UInteger) As LongInt
Dim As UInteger a = 0, b = 1
While Not (n <= 1) '' end condition of iterative loop
n = n - 1
Swap a, b
b = b + a
Wend
Return b * n
End Function
4. 非末尾再帰をより複雑な繰返しに置き換える
再帰手続きは、少なくとも 1つの再帰呼び出しと、それに続く、少なくとも 1つの命令がある場合、非末尾再帰手続きとなります。
非末尾再帰は、通常、単純な反復には変換できませんが、すでに末尾再帰に変換されている可能性もあります。
実行スタックサイズによる制限を避けるために、非末尾再帰的アルゴリズムは、通常は再帰手続きに渡されるパラメータを独自のストレージ・スタックにプッシュすることで、常に(少なくとも簡単に)繰返しアルゴリズムに置き換えることができます。
実際に、実行スタックはユーザースタック(サイズの制限が少ない)で置き換えられます。
以下の例では、次のユーザースタック・マクロ(
DynamicUserStackTypeCreateMacro.bi 任意のデータ型と互換性あり)を使っています:
'' "DynamicUserStackTypeCreateMacro.bi" として保存します
#macro DynamicUserStackTypeCreate(typename, datatype)
Type typename
Public:
Declare Constructor () '' pre-allocating user stack memory
Declare Property push (ByRef i As datatype) '' pushing on the user stack
Declare Property pop () ByRef As datatype '' popping from the user stack
Declare Property used () As Integer '' outputting number of used elements in the user stack
Declare Property allocated () As Integer '' outputting number of allocated elements in the user stack
Declare Destructor () '' deallocating user stack memory
Private:
Dim As datatype ae (Any) '' array of elements
Dim As Integer nue '' number of used elements
Dim As Integer nae '' number of allocated elements
Dim As Integer nae0 '' minimum number of allocated elements
End Type
Constructor typename ()
This.nae0 = 2^Int(Log(1024 * 1024 / SizeOf(datatype)) / Log(2) + 1) '' only a power of 2 (1 MB < stack memory < 2 MB here)
This.nue = 0
This.nae = This.nae0
ReDim This.ae(This.nae - 1) '' pre-allocating user stack memory
End Constructor
Property typename.push (ByRef i As datatype) '' pushing on the user stack
This.nue += 1
If This.nue > This.nae0 And This.nae < This.nue * 2 Then
This.nae *= 2
ReDim Preserve This.ae(This.nae - 1) '' allocating user stack memory for double used elements at least
End If
This.ae(This.nue - 1) = i
End Property
Property typename.pop () ByRef As datatype '' popping from the user stack
If This.nue > 0 Then
Property = This.ae(This.nue - 1)
This.nue -= 1
If This.nue > This.nae0 And This.nae > This.nue * 2 Then
This.nae \= 2
ReDim Preserve This.ae(This.nae - 1) '' allocating user stack memory for double used elements at more
End If
Else
Static As datatype d
Dim As datatype d0
d = d0
Property = d
AssertWarn(This.nue > 0) '' warning if popping while empty user stack and debug mode (-g compiler option)
End If
End Property
Property typename.used () As Integer '' outputting number of used elements in the user stack
Property = This.nue
End Property
Property typename.allocated () As Integer '' outputting number of allocated elements in the user stack
Property = This.nae
End Property
Destructor typename '' deallocating user stack memory
This.nue = 0
This.nae = 0
Erase This.ae '' deallocating user stack memory
End Destructor
#endmacro
非末尾再帰的手続き(non-tail)から繰返し手続きへの極めて単純な変換
末尾のない再帰的手続きは、再帰的呼び出しが実行コードの最後に置かれたときに最後になります(複数の再帰的呼び出しの前後に実行可能な命令行はありません)。
以下の 3つの例では、再帰呼び出しは常に実行コードブロックの最後にあり、順序の制約がないので、再帰手続きから繰返し手続きへの変換は非常に簡単です:
- 手続きのパラメータ(および関数の戻り値)をローカルなものにする。
- パラメータの初期値をユーザスタックに格納します。
- While ... Wend ループに入れて、ユーザースタックを空にします:
- ユーザースタックから変数を取り出します。
- 再帰手続き本体と同様に変数を処理します。
- 再帰関数の "return" 変数を蓄積します(最終値は関数本体の終了時に返されます)。
- 対応する変数をユーザースタックにプッシュして、再帰呼び出しを置き換えます。
最初の例(実行画面用):組合せ係数 nCp の計算(二項係数の計算)と Pascal の三角形を表示:
最初の関数
recursiveCombination は再帰形式です(最後のアクティブな命令文に、合計を伴う 2つの再帰呼び出しがあるので、末尾再帰ではありません)。
2番目の関数
translationToIterativeCombinationStack は、独自のスタックを使った繰返し形式です。
この 2つの関数では、類似した構造が保存されており、変換方法を啓発しています。
再帰関数から繰返し積み上げ関数へ:
- 先行して、累算器用のローカル変数を 1つ宣言する。
- 2 つの初期パラメータ値をユーザスタックにプッシュする。
- While ... Wend ループに入ってユーザスタックを空にする。
- ユーザー・スタックからパラメータを引き出す。
- Return 1 は cumul = cumul + 1 に置き換えられる。
- Return recursiveCombination(n - 1, p) + recursiveCombination(n - 1, p - 1) は S.push = n - 1 : S.push = p and S.push = n - 1 : S.push = p - 1 に置き換えられる。
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
'---------------------------------------------------------------------------
#Include
"DynamicUserStackTypeCreateMacro.bi"
DynamicUserStackTypeCreate
(DynamicUserStackTypeForUinteger,
UInteger)
Function translationToIterativeCombinationStack
(ByVal n
As UInteger,
ByVal p
As UInteger) As LongInt
Dim cumul
As LongInt =
0
Dim As DynamicUserStackTypeForUinteger S
S.push = n : S.push = p
While S.used >
0
p = S.pop : n = S.pop
If p =
0 Or p = n
Then
cumul = cumul +
1
Else
S.push = n -
1 : S.push = p
S.push = n -
1 : S.push = p -
1
End If
Wend
Return cumul
End Function
'---------------------------------------------------------------------------
Sub Display
(ByVal Combination
As Function (ByVal n
As UInteger,
ByVal p
As UInteger) As LongInt,
ByVal n
As Integer)
For I
As UInteger =
0 To n
For J
As UInteger =
0 To I
Locate ,
6 * J +
3 *
(n - I
) +
3
Print Combination
(I, J
);
Next J
Print
Next I
End Sub
'---------------------------------------------------------------------------
Print " recursion:";
Display
(@recursiveCombination,
12)
Print
Print
Print " iteration with own storage stack:";
Display
(@translationToIterativeCombinationStack,
12)
Sleep
2つ目の例(描画画面用)、非末尾再帰サブルーチン(円の再帰的描画)を使用:
同様の変換手順:
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
'---------------------------------------------------------------------------
#Include
"DynamicUserStackTypeCreateMacro.bi"
DynamicUserStackTypeCreate
(DynamicUserStackTypeForInteger,
Integer)
Sub recursiveToIterativeCircleStack
(ByVal x
As Integer,
ByVal y
As Integer,
ByVal r
As Integer)
Dim As DynamicUserStackTypeForInteger S
S.push = x : S.push = y : S.push = r
Do While S.used >
0
r = S.pop : y = S.pop : x = S.pop
Circle (x, y
), r
If r >
16 Then
S.push = x + r /
2 : S.push = y : S.push = r /
2
S.push = x - r /
2 : S.push = y : S.push = r /
2
S.push = x : S.push = y + r /
2 : S.push = r /
2
S.push = x : S.push = y - r /
2 : S.push = r /
2
End If
Loop
End Sub
'---------------------------------------------------------------------------
Screen 12
Locate 2,
2
Print "recursion:"
recursiveCircle
(160,
160,
150)
Locate 10,
47
Print "iteration with own storage stack:"
recursiveToIterativeCircleStack
(480,
320,
150)
Sleep
3番目の例(実行画面用)、非末尾再帰サブルーチン(クイックソート・アルゴリズム)を使用:
同様の変換手順:
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
#Include
"DynamicUserStackTypeCreateMacro.bi"
DynamicUserStackTypeCreate
(DynamicUserStackTypeForInteger,
Integer)
Sub translationToIteraticeQuicksortStack
(ByVal L
As Integer,
ByVal R
As Integer)
Dim As DynamicUserStackTypeForInteger S
S.push = L : S.push = R
While S.used >
0
R = S.pop : L = S.pop
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
S.push = L : S.push = I -
1
End If
If R > J +
1 Then
S.push = J +
1 : S.push = R
End If
Wend
End Sub
Randomize
For I
As Integer =
LBound(t
) To UBound(t
)
t
(i
) =
Int(Rnd *
256)
Next I
Print "raw memory:"
For K
As Integer =
LBound(t
) To UBound(t
)
Print Using "####"; t
(K
);
Next K
Print
recursiveQuicksort
(LBound(t
),
UBound(t
))
Print "sorted memory by recursion:"
For K
As Integer =
LBound(t
) To UBound(t
)
Print Using "####"; t
(K
);
Next K
Print
Print
Randomize
For I
As Integer =
LBound(t
) To UBound(t
)
t
(i
) =
Int(Rnd *
256)
Next I
Print "raw memory:"
For K
As Integer =
LBound(t
) To UBound(t
)
Print Using "####"; t
(K
);
Next K
Print
translationToIteraticeQuicksortStack
(LBound(t
),
UBound(t
))
Print "sorted memory by iteration with stack:"
For K
As Integer =
LBound(t
) To UBound(t
)
Print Using "####"; t
(K
);
Next K
Print
Sleep
非最終再帰手続きから繰返し手続きへの変換はもう少し複雑
これらの例では、再帰呼び出しが実行されたコードの最後に配置されていないので、非最終再帰手続きから繰返し手続きへの変換は少し複雑になります。
以下で使う一般的な方法は、まず元の再帰的手続きを「最終」再帰的手続きに変換することです。つまり、再帰呼び出しを、実行コードブロックの最後(前後に実行可能な命令行がない)に配置します。
最初の例(実行画面用)、非末尾再帰的サブルーチン(ハノイの塔アルゴリズム)を使用:
この例では、2つの再帰呼び出しは、実行されるコードブロックの最後にありますが、命令行で区切られており、順序に制約があります。
この 2つの関数では、同様の構造が維持されているので、比較して変換方法の参考になります。
再帰関数から繰返し積層関数へ:
- 最初のステップは、再帰コード本体の先頭に同等のものを追加して、2つの再帰呼び出しの間の命令行を、削除することです(対応する有用なデータを渡すために 2つのパラメータが手続きに追加されます)。
- 次に、繰返し形式への変換プロセスは、前述の例(独自のストレージ・スタックを使用)と同様ですが、ストレージ・スタックにプッシュするときに、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
Sub finalRecursiveHanoi
(ByVal n
As Integer,
ByVal departure
As String,
ByVal middle
As String,
ByVal arrival
As String,
ByVal dep
As String =
"",
ByVal arr
As String =
"")
If dep <>
"" Then Print " move one disk from " & dep &
" to " & arr
If n >
0 Then
finalRecursiveHanoi
(n -
1, departure, arrival, middle,
"")
finalRecursiveHanoi
(n -
1, middle, departure, arrival, departure, arrival
)
End If
End Sub
#Include
"DynamicUserStackTypeCreateMacro.bi"
DynamicUserStackTypeCreate
(DynamicUserStackTypeForString,
String)
Sub translationToIterativeHanoi
(ByVal n
As Integer,
ByVal departure
As String,
ByVal middle
As String,
ByVal arrival
As String)
Dim As String dep =
"", arr =
""
Dim As DynamicUserStackTypeForString S
S.push =
Str(n
) : S.push = departure : S.push = middle : S.push = arrival : S.push = dep : S.push = arr
While S.used >
0
arr = S.pop : dep = S.pop : arrival = S.pop : middle = S.pop : departure = S.pop : n =
Val(S.pop
)
If dep <>
"" Then Print " move one disk from " & dep &
" to " & arr
If n >
0 Then
S.push =
Str(n -
1) : S.push = middle : S.push = departure : S.push = arrival : S.push = departure : S.push = arrival
S.push =
Str(n -
1) : S.push = departure : S.push = arrival : S.push = middle : S.push =
"" : S.push =
""
End If
Wend
End Sub
Print "recursive tower of Hanoi:"
recursiveHanoi
(3,
"A",
"B",
"C")
Print
Print "final recursive tower of Hanoi:"
finalRecursiveHanoi
(3,
"A",
"B",
"C")
Print
Print "iterative tower of Hanoi:"
translationToIterativeHanoi
(3,
"A",
"B",
"C")
Print
Sleep
2つ目の例(実行画面用)、テールではない再帰的サブルーチンを使用(n からカウントダウンし、n までカウントアップし直す):
この例では、再帰呼び出しの後、実行されたコードブロックが終了する前に命令行があります。
2つの関数は、同様の構造になっているので、変換方法を理解できます。
再帰関数から繰返し積み上げ関数へ:
- 最初のステップは、実行されたコードブロックの最後にある命令行を、新しい再帰呼び出し(対応する有用なデータを渡すために、パラメータが手続きに追加されます)に置き換えることです。
- 再帰コード本体の先頭には、同等の命令行(渡されたデータを使う)が追加され、この場合、通常のコードの代わりに実行されます。
- その後、繰返し形式への変換プロセスは、前の例(独自のストレージ・スタックを使用)と同様で、ストレージ・スタックにプッシュするときに 2つの再帰呼び出しの順序を逆にします。
Sub recursiveCount
(ByVal n
As Integer)
If n >=
0 Then
Print n &
" ";
If n =
0 Then Print
recursiveCount
(n -
1)
Print n &
" ";
End If
End Sub
Sub finalRecursiveCount
(ByVal n
As Integer,
ByVal recount
As String =
"")
If recount <>
"" Then
Print recount &
" ";
Else
If n >=
0 Then
Print n &
" ";
If n =
0 Then Print
finalRecursiveCount
(n -
1,
"")
finalRecursiveCount
(n -
1,
Str(n
))
End If
End If
End Sub
#Include
"DynamicUserStackTypeCreateMacro.bi"
DynamicUserStackTypeCreate
(DynamicUserStackTypeForString,
String)
Sub translationToIterativeCount
(ByVal n
As Integer)
Dim As String recount =
""
Dim As DynamicUserStackTypeForString S
S.push =
Str(n
) : S.push = recount
While S.used >
0
recount = S.pop : n =
Val(S.pop
)
If recount <>
"" Then
Print recount &
" ";
Else
If n >=
0 Then
Print n &
" ";
If n =
0 Then Print
S.push =
Str(n -
1) : S.push =
Str(n
)
S.push =
Str(n -
1) : S.push =
""
End If
End If
Wend
End Sub
Print "recursive counting-down then re-counting up:"
recursiveCount
(9)
Print
Print
Print "final recursive counting-down then re-counting up:"
finalRecursiveCount
(9)
Print
Print
Print "iterative counting-down then re-counting up:"
translationToIterativeCount
(9)
Print
Print
Sleep
他の自明でない再帰的手続きから繰返し手続きへの変換
再帰から繰返しへの変換の他の2つのケースを、簡単な例を使ってここで紹介します:
- 相互再帰の場合。
- 入れ子になった再帰の場合。
2 つの関数は、1 番目の関数が 2 番目の関数を呼び出し、さらに 2 番目の関数が 1 番目の関数を呼び出す場合、相互に再帰的であるといいます。
関数に渡される引数が、その関数自体を参照する場合、再帰関数は入れ子になっているといいます。
相互再帰関数('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
#Include
"DynamicUserStackTypeCreateMacro.bi"
DynamicUserStackTypeCreate
(DynamicUserStackTypeForInteger,
Integer)
Function iterativeIsEven
(ByVal n
As Integer) As Boolean
Dim As Integer i =
1
Dim As DynamicUserStackTypeForInteger S
S.push = n : S.push = i
While S.used >
0
i = S.pop : n = S.pop
If i =
1 Then
If n =
0 Then
Return True
Else
S.push = n -
1 : S.push =
2
End If
ElseIf i =
2 Then
If n =
0 Then
Return False
Else
S.push = n -
1 : S.push =
1
End If
End If
Wend
End Function
Function iterativeIsOdd
(ByVal n
As Integer) As Boolean
Dim As Integer i =
2
Dim As DynamicUserStackTypeForInteger S
S.push = n : S.push = i
While S.used >
0
i = S.pop : n = S.pop
If i =
1 Then
If n =
0 Then
Return True
Else
S.push = n -
1 : S.push =
2
End If
ElseIf i =
2 Then
If n =
0 Then
Return False
Else
S.push = n -
1 : S.push =
1
End If
End If
Wend
End Function
Print recursiveIsEven
(16), recursiveIsOdd
(16)
Print recursiveIsEven
(17), recursiveIsOdd
(17)
Print
Print iterativeIsEven
(16), iterativeIsOdd
(16)
Print iterativeIsEven
(17), iterativeIsOdd
(17)
Print
Sleep
入れ子の再帰関数を用いた例('Ackermann()' 関数):
入れ子型再帰関数から繰返しスタック関数へ:
- 1 つのパラメータに対する入れ子の呼び出しのために、2 つの独立したストレージスタックを使います。関数の第 1 パラメータ m と第 2 パラメータ n のためです。
- Return expression は、入れ子呼び出しが行われているパラメータ専用のスタックに式をプッシュするように変換されます。
- したがって、同じスタックからポッピングされるデータの Return が、コードの最後に追加されます。
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
#Include
"DynamicUserStackTypeCreateMacro.bi"
DynamicUserStackTypeCreate
(DynamicUserStackTypeForInteger,
Integer)
Function iterativeAckermann
(ByVal m
As Integer,
ByVal n
As Integer) As Integer
Dim As DynamicUserStackTypeForInteger Sm, Sn
Sm.push = m : Sn.push = n
While Sm.used >
0
m = Sm.pop : n = Sn.pop
If m =
0 Then
Sn.push = n +
1 ' Return n + 1 (and because of nested call)
Else
If n =
0 Then
Sm.push = m -
1 : Sn.push =
1 ' Return Ackermann(m - 1, 1)
Else
Sm.push = m -
1 : Sm.push = m : Sn.push = n -
1 ' Return Ackermann(m - 1, Ackermann(m, n - 1))
End If
End If
Wend
Return Sn.pop
' (because of Sn.push = n + 1)
End Function
Print recursiveAckermann
(3,
0), recursiveAckermann
(3,
1), recursiveAckermann
(3,
2), recursiveAckermann
(3,
3), recursiveAckermann
(3,
4)
Print iterativeAckermann
(3,
0), iterativeAckermann
(3,
1), iterativeAckermann
(3,
2), iterativeAckermann
(3,
3), iterativeAckermann
(3,
4)
Sleep
参照: