使用状態機で再帰を除去する

1. 再帰の概要#

再帰は、関数が自身を呼び出す方法であり、コンピュータプログラムの実行メカニズム（つまり、コンピュータが同じ問題を解決するのに適していること）を利用して、コードを大幅に簡略化することができます。たとえば、階乗を再帰的に実装する場合：

long long factorial(int n) {
    if(n == 1) return 1; // 再帰の基準（出口）
    return n * factorial(n - 1);
}

2. 再帰の効率#

再帰は、システムのメモリスタックを使用して実装されるため、関数を呼び出す際には、関数の引数と戻りアドレスをスタックにプッシュする必要があります。そのため、再帰関数を呼び出すと、一定のオーバーヘッドが発生し、前回の関数呼び出しの状態（実行状態と変数の値）を保存するための主なオーバーヘッドが発生します。そのため、呼び出し回数が多すぎると、大量のスタックスペースを占有し、スタックオーバーフローの問題が発生する可能性があります。したがって、純粋に効率の問題について議論すると、再帰は非常に良い設計パターンではありません。

3. 一般的な再帰アルゴリズム#

一般的な再帰アルゴリズムは多数ありますが、主に「分割統治法」と「減少統治法」の 2 つの戦略に分けられます。

分割統治法は、大規模な問題を解決するために、通常は 2 つの（一般的には 2 つの）サブ問題に分割し、2 つの問題のサイズがほぼ同じであると仮定します。サブ問題の解から元の問題の解を得ることができます。

// 二分法による合計の計算
int sum(int A[], int low, int high)
{
return (low == high) ? A[low] : sum(A, low, (low + high) >> 1) + sum(A, ((low + high) >> 1) + 1, high);
}

減少統治法は、大規模な問題を解決するために、1 つは自明な問題であり、もう 1 つはサイズが小さくなります。サブ問題の解から元の問題の解を得ることができます。

// 再帰的な配列の合計の計算
int sum(int A[], int n)
{
    return (n < 1) ? 0 : A[n - 1] + sum(A, n-1);
}

マージソート、クイックソート、検索などのアルゴリズムは、分割統治法を使用しています。

また、再帰を使用すると問題の簡略化が非常に効果的であることにも気付きましたが、同時にリソースのオーバーヘッドも増加することにも気付きました。そのため、アルゴリズムを設計する際には、いくつかの最適化方法があります。例えば：

非末尾再帰関数を末尾再帰関数に変換する（一部の言語ではサポートされていない場合があります）
再帰的な式（トップダウン）を反復的な式（ボトムアップ）に変換する
再帰をエミュレートするためにステートマシンなどの方法を使用して再帰を除去する

末尾再帰：
関数内のすべての再帰呼び出しが関数の最後に出現し、その返り値が式の一部ではない場合、その再帰呼び出しは末尾再帰と呼ばれます。末尾再帰関数の特徴は、戻りの過程で何の操作も行わないことです。この特性は非常に重要であり、ほとんどの現代のコンパイラは、この特性を利用して最適化されたコードを自動生成します。

4. ステートマシンの概念#

ステートマシン：

ステートマシンは、有限状態オートマトンの略称であり、現実の事物の動作規則を抽象化した数学モデルです。

2 つのタイプに分けられます。1 つはムーア型、もう 1 つはミーリー型で、主な違いは、ムーア型ステートマシンの出力はシステムの内部状態のみに依存し、ミーリー型の出力は入力とシステムの内部状態の両方に依存することです。

まず、「状態」（ State ）とは何かを説明しましょう。現実の事物にはさまざまな状態があります。たとえば、自動ドアには open と closed の 2 つの状態があります。通常、ステートマシンは有限状態マシンと呼ばれ、記述される事物の状態の数が有限であることを意味します。たとえば、自動ドアの状態は open と closed の 2 つです。

ステートマシン、またはステートマシン（ State Machine ）とは、実際のマシンを指すのではなく、数学モデルを指します。要するに、通常はステート遷移図と呼ばれるグラフです。たとえば、自動ドアの動作規則に基づいて、次のようなグラフを抽象化することができます。

自動ドアには open と closed の 2 つの状態があります。closed の状態では、ドアを開く信号が読み取られると、状態が open に切り替わります。open の状態では、ドアを閉じる信号が読み取られると、状態が closed に切り替わります。

このように、再帰のステートマシンを使用することで、スタックデータ構造を使用し、システムスタックを使用せずに再帰の計算を完了することができます。ここでは、階乗の再帰的な計算を例に説明します。

#include <iostream>
#include <stack>

struct Data {
    int num; // メソッドの引数
    int return_address; // メソッドの戻りアドレス、ここでは使用しない
};

std::stack<Data> my_stk;

int execute_factorial(int n) {
    int state = 1; // 初期状態は1
    int res = 1; 
    while(state != 6) { // 状態が6になるまで再帰を続ける
        switch(state) {
            case 1: // 再帰の初期化状態
                state = 2;
                break;
            case 2: // 再帰の出口条件を満たしているかどうかを判断
                if(n <= 1) {  
                    res = 1;
                    state = 4; // 再帰プロセスが完了し、バックトラック状態に入る
                } else 
                    state = 3; // 再帰プロセスを続ける

                break;
            case 3: // 再帰のスタックにプッシュ
                my_stk.push({n, 0});
                --n; // 再帰ごとにnを1減らす
                state = 2;
                break;
            case 4: // スタックが空かどうかを確認
                if(my_stk.empty())
                    state = 6;
                else
                    state = 5;
                break;
            case 5: // バックトラックプロセス
                Data tmp =my_stk.top();
                my_stk.pop();
                res *= tmp.num;
                state = 4;
                break;
        }
    }
    return res;
}

int main()
{
    std::cout << execute_factorial(0) << std::endl;
    return 0;
}

上記のコードは、ステートマシンを使用して再帰を除去しています。再帰版の階乗と反復版の階乗、およびステートマシン版の階乗を比較すると、再帰ロジックが比較的単純な場合、通常は再帰を反復に変換します。再帰ロジックが複雑な場合、ステートマシンを使用して再帰を除去することができます。コード量は多少増えるかもしれませんが、いくつかの場合（再帰式が推測困難であるか、または再帰式を推測できない場合など）では、再帰を非常に簡単にすることができます。