FreeBASIC マニュアルのトップに戻る

FreeBASIC ProPgRecursionIteration

目次→教本→プログラマーのための案内Replace Recursion with Iteration←オリジナル・サイト

再帰を繰返しに置き換える 左にメニュー・フレームが表示されていない場合は、ここをクリックして下さい

←リンク元に戻る プログラム開発関連に戻る

あらゆる再帰を単純な繰返し置き換える方法、あるいは無制限の繰返しを独自のスタックに置き換える方法。

序文:
繰返しと再帰は、特にあるスクリプトを一定回数実行することで、コードの最適化を可能にする、プログラムを組む上で非常に便利な 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 - 1result * 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 1cumul = 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


このページの頭に戻る



参照:
プログラマーのための案内に戻る
←リンク元に戻る プログラム開発関連に戻る

ページ歴史:2020-08-08 13:05:12
日本語翻訳:WATANABE Makoto、原文著作者:fxm

ホームページのトップに戻る

表示-非営利-継承