序文
私は本を読んでいたときに最近この内容を見ました、そして、私は非常にやりがいがありました。反復は、ループ(while、do ... wile)またはイテレーターを使用します。これは、ループ条件が満たされないときに終了します。再帰は一般に関数の再回帰であり、それ自体または非直接的に呼び出すことができます。つまり、メソッドA呼び出し方式b、およびメソッドBはメソッドAを順番に呼び出し、再帰出口の条件はIFおよびelseステートメントであり、条件が基礎を満たしているときに終了します。
上記は、反復と再帰の構文特性です。 Javaのそれらの違いは何ですか?以下のこの記事の詳細をご覧ください。
1。再帰
反復に関しては、数学的な式について言及する必要があります: n!=n*(n-1)*(n-2)*...*1
要因を計算するには多くの方法があります。特定の数学的基盤を持っている人は誰でもn!=n*(n-1)!したがって、コードの実装は、次のように直接記述できます。
コード1
int factorial(int n){if(n == 1){return 1; } else {return n*factorial(n-1); }}上記のコードを実行するとき、マシンは実際に一連の乗算を実行する必要があります: factorial(n) → factorial(n-1) → factorial(n-2) →…→ factorial(1) 。したがって、(最後の計算の結果を追跡する)(最後の計算の結果を追跡する)と、計算を実行する(乗算チェーンの構築)を追跡する必要があります。絶えずそれ自体と呼ばれるこのタイプの操作は、再帰と呼ばれます。再帰は、線形再帰と数値再帰にさらに分割することができます。情報の量は、アルゴリズムの入力とともに直線的に増加します。再帰は線形再帰と呼ばれます。 nを計算します! (工場)は線形再帰です。 Nが増加すると、計算に必要な時間が直線的に増加するためです。入力の増加とともに指数関数的に成長する別のタイプの情報は、ツリー再帰と呼ばれます。
2。反復
nを計算する別の方法! IS:最初に1を計算して2を掛けてから、結果に3を掛け、次に結果に4を掛け、Nまで乗算します。プログラムの実装中に、カウンターを定義できます。乗算が実行されるたびに、カウンターの値がNに等しくなるまでカウンターが一度増加します。コードは次のとおりです。
コード2
int factorial(int n){int product = 1; for(int i = 2; i <n; i ++){product *= i; } return product;}コード1と比較して、コード2は乗算チェーンを構築しません。計算の各ステップを実行する場合、現在の結果(製品)とiの値を知る必要があります。この形式の計算は、反復と呼ばれます。反復にはいくつかの条件があります。1。初期値を持つ変数があります。 2。変数値がどのように更新されるかを説明するルール。 3。終了条件。 (ループの3つの要素:ループ変数、ループボディ、ループ終了条件)。再帰と同じ。入力が直線的に成長するにつれて線形になる時間要件は、線形反復と呼ばれます。
3。反復対再帰
2つのプログラムを比較した後、特に数学的な機能の観点から、それらはほぼ同じように見えることがわかります。 n!を計算する場合、それらの計算ステップはnの値に比例します。ただし、プログラムの視点を取り、それらの実行方法を検討すると、2つのアルゴリズムは非常に異なります。
(注:元のテキストは違いについて少し無関係であるため、ここでは翻訳しません。以下は著者自身の要約です。)
まず第一に、再帰を分析します。実際、再帰の最大のことは、複雑なアルゴリズムをいくつかの同一の再現可能なステップに分解することです。したがって、再帰を使用して計算ロジックを実装するには、多くの場合、解決するために非常に短いコードのみが必要であり、そのようなコードは理解しやすくなります。ただし、再帰とは、多数の関数呼び出しを意味します。関数呼び出しのローカル状態がスタックを使用して記録される理由。したがって、これは多くのスペースを無駄にする可能性があり、再帰が深すぎる場合、スタックオーバーフローを引き起こす可能性があります。
次に、反復を分析します。実際、再帰は反復に置き換えることができます。ただし、再帰の単純さと理解と比較して、反復はより厳格で理解が困難です。特に、より複雑なシナリオに遭遇する場合。ただし、コードを理解することの難しさは、より明白なポイントももたらします。反復の効率は再帰よりも高く、宇宙消費量も比較的少ないです。
再帰には反復が必要ですが、反復の再帰はない場合があり、それらのほとんどは互いに変換することができます。
反復を使用できる場合は、再帰を使用しないでください。再帰的に関数を再帰的に浪費するだけでなく、再帰が深すぎる場合、簡単にスタックオーバーフローを引き起こす可能性があります。
4。数字の再帰
前述のように、ツリーが再帰的である情報の量は、入力の増加とともに指数関数的に増加します。フィボナッチシーケンスは典型的な例です。
テキストの説明では、フィボナッチ配列の最初の2つの数値の合計は、3番目の数値に等しくなります:0、1、2、3、5、8、13、21 ...
再帰実装コードは次のとおりです。
int fib(int n){if(n == 0){return 0; } else if(n == 1){return 1; } else {return fib(n-1) + fib(n-2); }}計算プロセス中、 fib(5)を計算するには、プログラムは最初にfib(4)およびfib(3)を計算する必要があります。 fib(4)を計算するには、プログラムは最初にfib(3)とfib(2)を計算する必要があります。 FIB(3)は、このプロセス中に2回計算されます。
上記の計算プロセスから、結論を描くことができます。再帰を使用してフィボナッチ配列に冗長な計算があります。
上記のように、再帰的アルゴリズムは一般に繰り返しによって実装でき、フィボナッチシーケンスの計算にも同じことが言えます。
int fib(int n){int fib = 0; int a = 1; for(int i = 0; i <n; i ++){int temp = fib; fib = fib + a; a =温度; } return fib;}再帰法では冗長な計算がありますが、反復に置き換えることができます。しかし、これは再帰を完全に置き換えることができるという意味ではありません。再帰は読みやすくなるためです。
要約します
上記は、この記事のコンテンツ全体です。この記事の内容が、Javaの学習や使用のすべての人に役立つことを願っています。ご質問がある場合は、メッセージを残してコミュニケーションをとることができます。