1. 再帰の紹介#
私たちは、再帰が自身を呼び出す方法であることを知っています。計算機プログラムの実行の自然なメカニズム（つまり、コンピュータが得意とするのは同じ問題を解決すること）を利用することで、コードを大幅に簡素化できます。例えば、再帰を使用して階乗を実装することができます：
long long factorial(int n) {
if(n == 1) return 1; // 再帰基（出口）
return n * factorial(n - 1);
}
2. 再帰の効率#
再帰はシステムメモリのスタックを使用して実現されるため、関数を呼び出す際には、関数の引数と関数の戻りアドレスをスタックにプッシュする必要があります。そのため、再帰関数を呼び出す際には一定のオーバーヘッドが発生します。主なオーバーヘッドは、前回の関数呼び出しの状態（実行状態と変数値）を保存するために使用されます。したがって、呼び出し回数が多すぎると、大量のスタックスペースを占有し、スタックオーバーフローの問題を引き起こす可能性があります。したがって、効率の問題を単純に議論する場合、再帰はあまり良い設計パターンではありません。
3. 一般的な再帰アルゴリズム#
一般的な再帰アルゴリズムは多くあり、主に分割統治法と減少統治法の 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);
}
減少統治法とは、大規模な問題を解決するために、それを 2 つのサブ問題に分割することを指します。一つは平凡な問題で、もう一つは規模が縮小された問題です。サブ問題の解から元の問題の解を得ます。
// 再帰的に配列の和を求める
int sum(int A[], int n)
{
return (n < 1) ? 0 : A[n - 1] + sum(A, n-1);
}
マージソート、クイックソート、検索などのアルゴリズムは、分割統治法を使用しています。
私たちはまた、再帰を使用することで問題を簡素化する効果が非常に良いことを観察しましたが、同時にリソースのオーバーヘッドも増加します。したがって、アルゴリズムを設計する際には、いくつかの最適化方法があります。例えば：
- 非末尾再帰関数を末尾再帰関数に変換する（部分的に言語がサポートしていない場合があります）
- 再帰的な表現（トップダウン）を再帰的でない表現（ボトムアップ）に変換する
- 状態機械などの方法を使用して再帰をシミュレートし、再帰を排除する
末尾再帰：
関数内のすべての再帰的な呼び出しが関数の末尾に出現する場合、その再帰関数は末尾再帰と呼ばれます。再帰呼び出しが関数本体の最後に実行される文であり、その戻り値が式の一部に属さない場合、この再帰呼び出しは末尾再帰です。末尾再帰関数の特徴は、戻る過程で何の操作も行わないことです。この特性は非常に重要です。なぜなら、ほとんどの現代のコンパイラはこの特性を利用して自動的に最適化されたコードを生成するからです。
4. 状態機械の概念#
状態機械:
状態機械は有限状態機械の略称であり、現実の事物の運用ルールを抽象化した数学モデルです。
2 種類に分かれます。一つはムーア型、もう一つはミーリー型で、主な違いは、ムーア型状態機械の出力はシステム内部の状態のみによって決定されるのに対し、ミーリー型の出力は入力とシステム内部の状態によって共同で決定されることです。
まず「状態」（State）とは何かを説明します。現実の事物は異なる状態を持っています。例えば、自動ドアには open と closed の 2 つの状態があります。私たちが通常言う状態機械は有限状態機械であり、記述される事物の状態の数は有限です。例えば、自動ドアの状態は open と closed の 2 つです。
状態機械、つまり State Machine は、実際の機械を指すのではなく、数学モデルを指します。言い換えれば、一般的には状態遷移図を指します。例えば、自動ドアの運用ルールに基づいて、以下のような図を抽象化できます。
自動ドアには 2 つの状態、open と closed があります。closed 状態で開門信号を読み取ると、状態は open に切り替わります。open 状態で閉門信号を読み取ると、状態は closed に切り替わります。
状態機械の正式名称は有限状態機械であり、「自動」という言葉には重要な意味が含まれています。状態機械が与えられ、同時にその現在の状態と入力が与えられると、出力状態は明確に計算できます。例えば、自動ドアの場合、初期状態が closed で、入力が「開門」であれば、次の状態は計算できます。
自動ドアには 2 つの状態、open と closed があります。closed 状態で開門信号を読み取ると、状態は open に切り替わります。open 状態で閉門信号を読み取ると、状態は closed に切り替わります。
これで状態機械の基本的な定義を紹介しました。
5. 状態機械を使用して再帰を排除する#
状態機械の概念を理解した後、システムが再帰関数を実行するプロセスを振り返りましょう：
- 再帰プロセス（トップダウン）：現在の状態が再帰出口条件を満たさない場合、現在の状態をスタックにプッシュし続け、再帰出口条件を満たすまで再帰を続けます。
- 戻りプロセス（ボトムアップ）：再帰ツリーの一分岐の再帰状態が終了した後、スタックに保存された内容をポップし、再帰表現を計算し続け、スタックが空になるまで戻ります。最後の計算結果を返します。
状態図を描くことができます：
このように、再帰の状態機械を利用し、データ構造スタックを使用してシステムスタックを使用せずに、全体の再帰計算を完了できます。ここでは、再帰的に階乗を計算する例を示します：
#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を減らす
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;
}
上記のコードは、状態機械を使用して再帰を排除しています。再帰版の階乗、再帰的でない版の階乗、状態機械版の階乗を比較すると、再帰の論理が比較的単純な場合、一般的には再帰を再帰的でないものに変換します。再帰の論理が比較的複雑な場合、状態機械を使用して再帰を排除することができます。コード量は少し増えますが、特定の状況（再帰的でない式を推測するのが難しい場合や、推測できない場合）では、再帰をうまく簡素化できます。