プロシージャまたは関数には、その中に別のプロシージャへの呼び出しを含めることができます。サブルーチン自体を呼び出すこともできます。この場合、コンピュータは気にしません。彼はいつものように、出会った命令を上から下まで一貫して実行します。
数学を覚えていれば、そこで数学的帰納法の原理に出会うことができます。それは次のとおりです。
あるステートメントは、すべての自然なnの場合に当てはまります。
1) n = 1 の場合に有効です。
2) 任意の自然 n = k に対するステートメントの妥当性から、n = k+1 についても真であることがわかります。
プログラミングではこの手法を再帰と呼びます
。
再帰は、指定された単純な基本ケースに基づいて、セット自体の観点からオブジェクトのセットを定義する方法です。
再帰的 は、それ自体を直接呼び出すか、他のプロシージャや関数を通じて呼び出すプロシージャ (関数) です。
再帰的プロシージャの例:
void Rec(int a)
{
if (a>0) { Rec(a-1); }
Console.WriteLine(a);
}
再帰の作業は、フローチャートとして概略的に表すことができます。
Rec() プロシージャはパラメータを指定して実行されます3 次に、パラメータ 3 のプロシージャ内で、パラメータ 2 のプロシージャが呼び出され、パラメータ 0 のプロシージャが呼び出されるまで同様に動作します。次に、制御はパラメータ 1 を持つプロシージャに戻り、数値 1 を出力して作業を終了します。パラメータ 3 のプロシージャの前。
呼び出されたすべてのプロシージャは、作業が完了するまでメモリに保存されます。同時プロシージャの数は再帰の深さと呼ばれます。
|
再帰とは、サブルーチンに含まれるコマンドを繰り返し実行することであることがわかりました。そして、これはサイクルの働きに似ています。 Prolog など、ループ構造がまったくないプログラミング言語もあります。
for のループの動作をシミュレートしてみましょう。
for ループにはステップ カウンター変数が含まれています。再帰的サブルーチンでは、このような変数をパラメータとして渡すことができます。
<プレ>
// 2 つのパラメータを持つプロシージャ LoopImitation()
// 最初のパラメータ –ステップ カウンター、2 番目のパラメーター –総ステップ数
static void LoopImitation(int i, int n)
{
Console.WriteLine("Hello N" + i); // 任意の値 i に対して繰り返されるステートメント
if (i < n) // ループカウンターがnに等しくなるまで、
{
LoopImitation(i+1, n); // 新しい呼び出しパラメータ i+1 を持つインスタンス プロシージャ (次の i 値に移動)<コード>
}
|
再帰と反復
再帰を理解するには、再帰を理解する必要があります...
プログラミングにおける 反復 - 周期的なデータ処理プロセスの 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 />
<本体>
| 再帰階乗関数 |
反復アルゴリズム |
<プレ>
static int Factorial(int n){
if (n > 1)
n * 階乗 (n - 1) を返します。
それ以外の場合は 1 を返します。
}
|
<プレ>
int x = 1;
for (int i = 2; i <= n; i++)
x = x * i;
Console.WriteLine("%d", x);
|
関数呼び出しには追加のオーバーヘッドがかかるため、非再帰階乗計算の方が若干高速になることを理解してください。
結論:再帰なしで単純な反復アルゴリズムを使用してプログラムを作成できる場合は、再帰なしで作成する必要があります。しかしそれでも、計算プロセスが再帰によってのみ実装される問題の大きなクラスが存在します。
一方、再帰的アルゴリズムは多くの場合、より理解しやすいものです。
ある数体系から別の数体系への数の再帰的変換
プロシージャ内のいくつかの状況では、引数なしで return という単語を使用できます。つまり、実際には、プロシージャはまだ何も返しません。 これは、再帰するときに便利です。 ; return は、再帰されるパラメーター値の基本ケースで下降を終了するために使用されます。たとえば、数値を 10 進数から 2 進数に変換する手順は次のようになります。
static void printTwo(int n)
{
もし (n == 0) リターン;
printTwo(n / 2);
if (n % 2 == 0) Console.Write(0);
else Console.Write(1);
}
|
タスク
「トゥンバ・ユンバ」族の言語のアルファベット。 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# プログラムは次のようになります。
// w - 変更可能なパラメータ (文字列-結果)
// TumbaWords プロシージャには、アルファベットが文字列として渡されます。
//単語単語と文字数が設定済み(先頭–0)
static void TumbaWords( string A, ref string w, int N )
{
if (N == w.Length) // w.Length - 文字列の文字数
{
// すべての文字がすでに単語に設定されている場合、
// その後、文字列を出力してプロシージャを終了する必要があります
Console.WriteLine(w);
戻る;
}
for ( int i = 0; i < w.Length; i ++ ) // 上記の条件が false の場合 (つまり、すべての文字が空白になっているわけではなく、
{
// 上記の条件が false の場合 (つまり、すべての文字にスペースが入っていない場合、
// 次に、ループ内でアルファベットのすべての文字を調べ、
// 最初の空きスペースに交互に文字を配置します
w += A[i];
TumbaWords(A, ref w, N+1);
w = w.Remove(w.長さ - 1); // 最後に追加された文字を削除し、
// 同じプレフィックスを持つ新しい単語を作成する
}
}
静的 void Main()
{
int n = Convert.ToInt32(Console.ReadLine());
文字列の単語 = "";
TumbaWords("KLMN", ref word, 0);
}
注意 w は変更可能なパラメータ (結果文字列) であることに注意してください。
|
|