1. 序章

このチュートリアルでは、再帰関数を反復形式に変換する方法について説明します。 テールとヘッドの再帰に適した変換方法と、任意の再帰を反復アルゴリズムに変換できる一般的な手法を紹介します。

2. 再帰

再帰には多くの利点があります。 多くの問題は再帰的な構造を持っており、より小さなサブ問題に分解できます。 したがって、サブ問題を再帰的に解決し、それらの解決策を組み合わせることは、そのような問題を処理するための自然な方法です。 そのため、再帰関数は読みやすく、理解しやすく、保守しやすいものです。

ただし、再帰には、独自のの問題がないわけではありません。 再帰呼び出しごとに新しいフレームが呼び出しスタックに追加されるため、非常に大きな入力を処理すると、再帰関数がスタックメモリを使い果たし、スタックオーバーフローエラーが発生する可能性があります。 さらに、再帰関数は、反復関数よりもメモリとスペースの複雑さが高くなる可能性があります。 フィボナッチ数を計算するための再帰関数と反復関数を見てみましょう。

再帰関数は、フィボナッチ数の定義に従うため、より読みやすくなります。

     

ただし、スタックの深さは制限されているため、大きな場合はオーバーフローが発生します。 対照的に、反復関数は同じフレームで実行されます。 さらに、再帰関数は指数関数的な時間計算量ですが、反復関数は線形です。 そのため、再帰的アルゴリズムを反復アルゴリズムに変換する必要がある場合があります。 読みやすさが失われると、パフォーマンスが向上します。

3. 末尾再帰関数の変換

処理する最も簡単なケースは、末尾再帰です。 このような関数は、再帰呼び出しが終了するまでに本体（非ベースブランチ）のすべての作業を完了します。そのため、その時点で他に何もすることはなく、その値を返す必要があります。 一般に、それらは同じパターンに従います。

アキュムレータは、実行中に部分的な解を保持する変数です。 これらは、一連のサブ問題の解決策を表しており、一方が他方の中にネストされています。 再帰がベースケースに達するまで、各呼び出しはアキュムレータを更新します。 その時点で、アキュムレータは、最初に解決し始めた問題全体の解決策を保持します。

3.1. 末尾再帰の反復バージョン

上記の末尾再帰のパターンには、次の反復バージョンがあります。

これから、変換の一般的なルールを定式化します。

  • whileループの前にアキュムレータを初期化します。
  • ベースケース条件の否定をループの条件として使用します。
  • whileループの本体として、再帰関数の本体（再帰呼び出しを除く）を使用します。
  • ループの後、アキュムレータのベースケース更新を適用し、その値を返します。

通常、ベースケースの更新はアキュムレータの値を変更しません。これは、多くの場合、0の加算や1の乗算などの中立的な操作になるか、適用する更新がないためです。 したがって、ほとんどの場合、この部分は無視できます。 それでも、ベースケースの更新が重要な関数を説明するために、それを擬似コードに保持します。 たとえば、複数の基本ケースがあり、それぞれが異なる値をアキュムレータと組み合わせる場合がこれに該当します。 ベースケースの更新がアキュムレータに依存している場合も同様です。

3.2. 例

これらのルールを使用して、階乗を計算するための末尾再帰関数を変換してみましょう。

ここで、反復バリアントで並べ替えるこの末尾再帰の要素を特定しましょう。

  • ベースケースの状態：
  • ベースケースのアキュムレータの更新：1を掛ける
  • アキュムレータの初期値：1
  • アキュムレータの更新：
  • 問題の軽減：から

これを念頭に置いて、次の反復関数を取得します。

の否定はの代わりになりますが、自然数に制限されているため、後者を使用します。

4. 一般的な変換方法

末尾再帰関数を反復に変える方法を見ました。 ただし、他の再帰タイプがあります。 たとえば、head-recursive関数は、再帰呼び出しを本体の終わりではなく先頭に配置します。 他のタイプは、入力を前処理し、呼び出しの戻り値を後処理するためのコードブロックで呼び出しを囲みます。 さらに、再帰関数は、1つだけでなく、その本体で任意の数の再帰呼び出しを行うことができます。

幸いなことに、再帰を反復アルゴリズムに変換する一般的な方法があります。 この方法は、フレームを呼び出しスタックにプッシュし、そこからポップすることによって再帰関数が実行されるという観察に基づいています。 したがって、スタックをシミュレートすると、単一のメインループで任意の再帰関数を繰り返し実行できます。 ただし、結果のコードはきれいではない場合があります。 そのため、通常、最初に関数を末尾再帰にしようとします。 成功すると、セクション3のメソッドを使用してかなり読みやすいコードを取得できます。 そうでない場合は、一般的な変換方法を使用します。 それでは、最初に再帰関数の一般的な形式を調べてみましょう。

4.1. 再帰の一般的な形式

再帰関数は、その本体で任意の数の再帰呼び出しを行うことができます。

この擬似コードは、バイナリツリートラバーサル（）のように、再帰呼び出し（）の数が一定または制限されている場合と、問題のサイズに依存する場合を対象としています。 また、ベースケースのソリューションは一定である場合もあれば、テストに合格したものに依存する場合もあります。 さらに、各非再帰コードブロックは、空または単一の命令にすることも、他のサブルーチンへの呼び出しを含めることもできます。 の目的は、-番目の再帰呼び出しのデータを準備することです。 最後に、再帰的なサブソリューションの組み合わせも一般的に理解する必要があります。それは、同じくらい単純な場合もあれば、より複雑な場合もあります。

4.2. 実行グラフ

を呼び出すたびにフレームが作成されます。 これは、渡されたパラメーター、ローカル変数、および戻り値のプレースホルダーを保持する構造体です。 フレームを視覚化して呼び出しを追跡すると、再帰関数が暗黙的で有向グラフを定義していることがわかります。 そのノードはフレームであり、その一部には外見のエッジがありません。 それらは、再帰の基本ケースを表しています。 その他には、内向きと外向きのエッジがあります。これらは、ベースケースと最初の呼び出しの間の呼び出しをモデル化します。 フィボナッチ番号のグラフの一部を見てみましょう。

からの有向エッジは、アクティブフレームを作成する再帰呼び出しに対応します。 したがって、再帰関数を実行することは、構造化された方法でフレームグラフをトラバースすることと同じです。 各エッジを2回交差します。1回目はのフレームを作成する呼び出しを行い、2回目は呼び出しの値をに返します。

4.3. 深さ優先探索としての実行

したがって、元の呼び出し元のフレームノードから開始し、最初の再帰呼び出しの前に非再帰コードブロックを実行します。 その時点で、呼び出しのフレームを表す子ノードを作成しました。 再帰が機能する方法は、子ノードに移動し、同じ方法でその子孫にアクセスする必要があることを意味します。 その後、フレームの戻り値を収集し、開始ノードに戻って、次の子に移動します。 目標は、すべてのノードにアクセスして最初のフレームに戻ることです。この時点で、子の戻り値を組み合わせて解を出力します。

しかし、このグラフは、再帰関数を反復関数に変換するのにどのように役立ちますか？ 答えは、実行グラフの深さ優先探索について説明したところにあります。 深さ優先トラバーサルの反復バージョンは、スタックを使用して、訪問用にマークされたノードを格納します。 関数の要素に対応する方法でノードとエッジを実装すると、反復バージョンが得られます。 そこでは、ノードを格納するためのスタックがCPUの呼び出しスタックの役割を果たします。

4.4. 実装の詳細

実行グラフは暗黙的です。 つまり、非再帰的なコードブロックを実行し、再帰的な呼び出しを行うときに、その場で作成します。 これを適切に行うには、変換する再帰関数の構造に従ってフレームとエッジを実装する必要があります。

したがって、最初の実行されていないNRCBと再帰呼び出しに関連付けられたエッジを返す必要があります。 また、エッジをたどって取得する子フレームへのポインタも含まれている必要があります。 したがって、この関数は問題をサブ問題に分割し、子フレームを作成する必要があります。 Aフレームは、そのローカル変数とそのサブ問題を保持できるデータ構造である必要があります。 また、戻り値を親に渡すことができる必要があります。

値を決定する責任があります。 フレームがベースケースノードの場合、関数は適切なベースケースソリューションを返す必要があります。 そうでない場合、関数はフレームがその子から取得した戻り値を組み合わせる必要があります。

4.5. 例

この再帰を反復に変換してみましょう。

4.6. フレーム、エッジ、およびエッジの作成

この例では、次のように作成するPython辞書である可能性があります。

def create_new_frame(n, parent, return_name):
    # create an empty frame
    frame = {
        'n' : None,
        'parent' : None,      # the parent frame
        'return_name' : None, # the return address
        'placeholders': {     # the placeholders for 
            'a' : None,   # the children's return values
            'c' : None
        },
        'local': {            # the local variables 
            'b' : None,
            'd' : None
        },
    }

    # fill in the fields
    frame['n'] = n 
    frame['parent'] = parent 
    frame['return_name'] = return_name
    return frame

Frame のインスタンスを関数と組み合わせて、戻り値を計算し、それをフレームの親に渡す必要があります。

def get_return_value(frame):
    if frame['n'] <= 1:
        # the base case
        return 1
    else:
        # the recursive case
        frame['local']['d'] = frame['placeholders']['a'] * frame['placeholders']['c']
        return frame['local']['d'] + 1

def pass_to_parent(frame, return_value):
    return_name = frame['return_name']
    frame['parent']['placeholders'][return_name] = return_value

この実装では、エッジをモデル化する必要はありません。 アルゴリズム7から、エッジには子フレーム（それが向けられているノード）と対応するNRCBが含まれている必要があることがわかります。 NRCBを整数としてモデル化し、別の整数フィールド nrcb_counter としてフレームに含め、 create_new_frame で0に初期化し、次の関数で解釈できます。

def execute_nrcb(frame):
    nrcb_counter = frame['nrcb_counter']
    if nrcb_counter == 1:
        # do nothing because the NRCB
        # before the first call (f(n-1))
        # is empty
        pass
    elif nrcb_counter == 2:
        frame['local']['b'] = frame['n'] // 2

カウンターを更新し、次の子フレームを返す関数で対応するNRCBを実行します。

def get_next_child(frame):
    # check if all the frame's NRCBs have been executed
    if frame['nrcb_counter'] >= 2:
        return None
    frame['nrcb_counter'] += 1
    execute_nrcb(frame)
    if frame['nrcb_counter'] == 1:
        child = create_new_frame(frame['n'] - 1, frame, 'a')
    else:
        child = create_new_frame(frame['placeholders']['b'], frame, 'c')
    return child

テストするフレームベースケースフレームではないことを確認し、 frame.nrcb_counter <2 。 コード全体は次のようになります。

def has_next_child(frame):
    return frame['n'] > 1 and frame['nrcb_counter'] < 2

def solve(n):
    start = create_new_frame(n, None, None)
    stack = [start]
    while len(stack) > 0:
        frame = stack.pop(-1)
        if has_next_child(frame):
            child = get_next_child(frame)
            stack.append(frame)
            stack.append(child)
        else:
            return_value = get_return_value(frame)
        if frame['parent'] is not None:
            pass_to_parent(frame, return_value)
    return get_return_value(start)

4.7. 読みやすさと意味論

フレーム、エッジ、および関連する関数の再帰固有の実装を使用して、一般的な深さ優先トラバーサルアルゴリズムを提供すると、変換したい再帰関数の反復バリアントが得られます。ただし、結果の反復コードは元の再帰的なものほど読みやすく、理解しやすいものではありません。

ただし、グラフにはいくつかのセマンティクスが保持されています。 これは元の問題の再帰的構造を具体化するため、それでも解釈できます。 子を持つノードは再帰の本体を表しますが、子がないノードでは基本ケースを認識できます。

4.8. 最適化と再帰の種類

最後に、グラフ内のいくつかのノードに複数回アクセスできることに注意してください。 これは、フィボナッチ数の場合のように、サブ問題が重複する場合に当てはまります。 とに依存しているので、2回訪問します。 同じノードに複数回アクセスすると、計算が繰り返され、複雑さが増します。 戻り値を覚えておくことで、この問題に対処できます。 ノードが返す必要のある値を計算するときはいつでも、それをノードに格納します。 後で同じノードにアクセスする場合は、すでに見つかったソリューションを再利用し、繰り返しの評価を回避します。 この手法はメモ化と呼ばれます。 一部の著者は、これを動的計画法のツールと見なしています。

さらに、実行グラフの形状は、さまざまな再帰タイプの違いを示しています。本体で再帰呼び出しを1回だけ行う再帰関数のグラフは、パスです。 2回の呼び出しを行い、サブ問題が重複しない場合、結果のグラフはバイナリツリーになります。 末尾再帰は、その再結合フェーズがID操作であるため、特定のものです。各ノードは、子の戻り値のみを転送します。 そのため、反復するためにスタックは必要ありません。

5. 結論

この記事では、再帰を反復に変換することについて説明しました。 再帰関数を反復関数に変換する一般的な方法を紹介しました。 また、末尾再帰のみの方法を示しました。 変換によってパフォーマンスが向上する場合でも、この方法ではコードの読みやすさが失われます。