プロシージャまたは関数には、その中に別のプロシージャへの呼び出しが含まれる場合があります。サブルーチン自体を呼び出すこともできます。この場合、コンピュータは気にしません。また、彼はいつものように、出会った命令を上から下まで一貫して実行します。
数学を覚えているなら、そこで 数学的帰納法の原理に出会うことができます。それは以下の通り です。
あるステートメントがすべての自然な n に対して true である場合
1. n = 1 および の場合に有効です。
2. 任意の自然な n = k に対するステートメントの妥当性から、 n = k+1 に対してそれが真であることがわかります。
プログラミングではこの手法を 再帰
と呼びます。
再帰は、指定された単純な基本ケースに基づいて、セット自体に関してオブジェクトのセットを定義する方法です。
再帰的は、それ自体を直接、または他のプロシージャや関数を通じて呼び出すプロシージャ (関数)とも呼ばれます
再帰的プロシージャの例:
<プレ>
void Rec(int a)
{
if (a>0) Rec(a-1);
cout << a;
}
再帰の作業はフローチャートで概略的に表すことができます。
Rec() プロシージャはパラメータ 3 で実行されます。次に、パラメータ 3 のプロシージャ内でパラメータ 2 のプロシージャが呼び出され、パラメータ 0 のプロシージャが呼び出されるまで同様に続きます。パラメータ 0 が呼び出された場合、再帰呼び出しはすでに行われず、パラメータ 0 を持つプロシージャは数値 0 を出力して終了します。次に、制御はパラメータ 1 を持つプロシージャに戻り、数値 1 を出力して作業を終了します。パラメータ 3 のプロシージャの前。
呼び出されたすべてのプロシージャは、作業が完了するまでメモリに保存されます。同時プロシージャの数は、再帰の深さと呼ばれます。
|
再帰。ループ シミュレーション
再帰とは、サブルーチンに含まれる命令を繰り返し実行することです。そして、これはサイクルの働きに似ています。 Prolog など、ループ構造がまったくないプログラミング言語もあります。
ループ for の動作をシミュレートしてみましょう。
for ループには、ステップ カウンター変数が含まれています。再帰サブルーチンでは、このような変数をパラメーターとして渡すことができます。
// 2 つのパラメータを持つ LoopImitation() プロシージャ。
// 最初のパラメータ –ステップ カウンター、2 番目のパラメーター –総ステップ数。
void LoopImitation(int i, int n)
{
cout << 「こんにちはN」 <<私は <<エンドル; // i の任意の値に対して繰り返される演算子
if (i < n) // ループ カウンターが n に等しくなるまで、
{ // パラメータ i+1 を使用してプロシージャの新しいインスタンスを呼び出します (次の値 i に移動します)。
LoopImitation(i + 1, n);
}
}
|
再帰と反復
再帰を理解するには、再帰を理解する必要があります...
プログラミングにおける 反復 - 周期的なデータ処理プロセスの 1 ステップ。
多くの場合、現在のステップ (反復) での反復アルゴリズムは、前のステップで計算された同じ操作またはアクションの結果を使用します。 そのような計算の一例は漸化関係の計算です。
再帰的な値の簡単な例は階乗です: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\)。
各ステップ (反復) での値の計算は \(N=N \cdot i\) です。 \(N\) の値を計算するときは、すでに保存されている値 \(N\) が使用されます。 >.
数値の階乗は、 漸化式を使用して記述することもできます。
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)
この説明は単なる再帰関数に過ぎないことに気づくかもしれません 。
ここで、最初の行 ( \(n <= 1\)) は基本ケース (再帰終了条件) であり、2 行目は次のステップへの移行です。 < br />
<本体>
| 再帰階乗関数 |
反復アルゴリズム |
|
int 階乗(int n)
{
if (n > 1)
n * 階乗 (n - 1) を返します。
それ以外の場合は 1 を返します。
}
|
x = 1;
for (i = 2; i <= n; i++)
x = x * i;
cout << x;
|
関数呼び出しには追加のオーバーヘッドがかかるため、非再帰階乗計算の方が若干高速になることを理解してください。
結論:再帰なしで単純な反復アルゴリズムを使用してプログラムを作成できる場合は、再帰なしで作成する必要があります。しかしそれでも、計算プロセスが再帰によってのみ実装される問題の大きなクラスが存在します。
一方、再帰的アルゴリズムの方が理解しやすい場合が多い
です。
タスク
「トゥンバ・ユンバ」族の言語のアルファベット。 4文字：「K」、「L」、「M」および「N」。このアルファベットの文字から作成できる n 文字で構成されるすべての単語を表示する必要があります。
この問題は通常の総当たり問題ですが、より小さな問題にまとめることができます。
単語を順次文字に置き換えて いきます。
単語の最初の位置は、アルファベットの 4 文字 (K、L、M、N) のいずれかになります。
最初に文字 K を置きましょう。次に、最初の文字 K を持つすべてのバリアントを取得するには、残りの n - 1 位置にある文字の可能な組み合わせをすべて列挙する必要があります。以下同様です。 (図を参照)。
したがって、問題は長さ n - 1 の 4 つの問題を解くことに帰着します。
n 文字を再帰的に繰り返す
w[0]='K'; // 最後の L-1 文字を反復処理します
w[0]='L'; // 最後の L-1 文字を反復処理します
w[0]='M'; // 最後の L-1 文字を反復処理します
w[0]='N'; // 最後の L-1 文字を反復処理します
w - 作業単語を格納する文字列。
したがって、再帰が得られました。 再帰手順の形式で問題の解決策を調整できます。
再帰がいつ終了するかを決定することはまだ残っています。全文字を設定した場合、つまり設定文字数はnとなります。この場合、結果の単語を画面に表示して手順を終了する必要があります
。
C++ プログラムは次のようになります。
#include
名前空間 std を使用します。
void TumbaWords( string A, string &w, int N )
// w - 変更可能なパラメータ (文字列-結果)
// TumbaWords プロシージャには、アルファベットが文字列として渡されます。
// 単語 word とすでに設定されている文字数 (先頭は – 0)。
{
int i;
if (N == w.size())
{
// すべての文字がすでに単語に設定されている場合、
// その後、文字列を出力してプロシージャを終了する必要があります
cout << w<<;エンドル;
戻る;
}
for ( i = 1; i < A.size(); i ++ )
{
// 上記の条件が false の場合 (つまり、すべての文字にスペースが入っていない場合)
// 次に、ループ内でアルファベットのすべての文字を調べ、
// 最初の空きスペースに交互に文字を配置します
w[N] = A[i];
TumbaWords ( A, w, N+1 );
}
}
主要（）
{
intn;
文字列;
intn;
シン>> n;
word.resize(n); // 文字列をサイズ n に増加します
TumbaWords( "KLMN", word, 0 );
}
注意 w は変更可能なパラメータ (結果文字列) であることに注意してください。
|
|