(Python) サブルーチン。再帰

再帰

プロシージャまたは関数には、その中に別のプロシージャへの呼び出しが含まれる場合があります。サブルーチン自体を呼び出すこともできます。この場合、コンピュータは気にしません。また、彼はいつものように、出会った命令を上から下まで一貫して実行します。

数学を覚えているなら、そこで数学的帰納法の原理に出会うことができます。それは以下の通り
です。 あるステートメントがすべての自然なn に対して true である場合
    1.n = 1 および
の場合に有効です。     2. 任意の自然な n = k に対するステートメントの妥当性から、n = k + 1 についても真であることがわかります。

プログラミングでは、 この手法を再帰
と呼びます。    

例

<プレ> <コード>def Rec(a): if (a>0): Rec(a-1) プリント(a)
再帰の作業を概略的にフローチャートで表すと



Rec() プロシージャはパラメータ 3 で実行されます。次に、パラメータ 3 のプロシージャ内でパラメータ 2 のプロシージャが呼び出され、パラメータ 0 のプロシージャが呼び出されるまで続きます。パラメータ 0 のプロシージャが呼び出されるとき、再帰呼び出しは発生しなくなり、パラメータ 0 を持つプロシージャは数値 0 を出力して終了します。次に、制御はパラメータ 1 を持つプロシージャに戻り、数値 1 を出力して作業を終了します。パラメータ 3 のプロシージャの前。

呼び出されたすべてのプロシージャは、作業が完了するまでメモリに保存されます。同時プロシージャの数は、再帰の深さと呼ばれます。
 

ループ置換としての再帰

再帰とは、サブルーチンに含まれる命令を繰り返し実行することです。そして、これはサイクルの働きに似ています。ループ構造がまったく存在しないプログラミング言語もあります。たとえば、プロローグ。
ループ for の動作をシミュレートしてみましょう。 
for ループには、ステップ カウンター変数が含まれています。再帰サブルーチンでは、このような変数をパラメーターとして渡すことができます。 <プレ> # 2 つのパラメータを持つプロシージャ LoopImitation() # 最初のパラメータ –ステップ カウンター、2 番目のパラメーター –総ステップ数 def LoopImitation(i, n): print("Hello N", i) # 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 行目は次のステップへの移行です。   <本体>
関数呼び出しには追加のオーバーヘッドがかかるため、非再帰階乗計算の方が若干高速になることを理解してください。

結論:再帰なしで単純な反復アルゴリズムを使用してプログラムを作成できる場合は、再帰なしで作成する必要があります。しかしそれでも、計算プロセスが再帰によってのみ実装される問題の大きなクラスが存在します。
一方、再帰的アルゴリズムの方が理解しやすい場合が多い
です。  

再帰階乗関数	反復アルゴリズム
デフォルト階乗(n): n > の場合1: n * 階乗 (n - 1) を返します それ以外：   1 を返す<​​/pre>	x=1 範囲内の i の場合 (1, n + 1): x = x * i;
タスク 部族の言語「Tumba-Yumba」のアルファベットでは、 4文字：「K」、「L」、「M」および「N」。このアルファベットの文字から組み立てられる n 文字で構成されるすべての単語を画面上に表示する必要があります この問題は通常の総当たり問題ですが、より小さな問題にまとめることができます。 単語を順次文字に置き換えて いきます。 単語の最初の位置は、アルファベットの 4 文字 (K、L、M、N) のいずれかになります。 まず、文字「K」を先頭に置きます。次に、最初の文字 'K' を持つすべてのバリアントを取得するには、残りの n-1 位置、および .etc (写真を参照) そこで、私たちは再帰的な解決策を思いつきました。ループ内で、考えられるすべての最初の文字を調べて (アルファベットの各文字を順番に最初に置きます)、それぞれのケースについて、考えられるすべての「尾部」を構築します。長さ n-1。   文字の再帰的反復 残りの部分が空 (n = 0) になった場合、再帰を停止し、完成した単語を出力する必要があります。すべての文字がすでに選択されています。 再帰的なプロシージャは次のようになります。 <プレ> def TumbaWords(単語、アルファベット、n): n <の場合1: 印刷(ワード) 戻る アルファベットの c の場合: TumbaWords(単語+c、アルファベット、n - 1) Training problem 行を繰り返す #1