34

Javaの反復メソッドよりも再帰メソッドの方が常に優れていますか?

また、繰り返しの代わりにいつでも使用できますか? その逆も可能ですか?

4

8 に答える 8

41

javaの反復メソッドよりも再帰メソッドの方が常に優れていますか?

いいえ

また、繰り返しの代わりにいつでも使用できますか? その逆も可能ですか?

再帰関数から反復関数をいつでも作成できます(メモリが処理できる場合は、こちらの興味深いリンクを参照してください)。

場合によっては、再帰を使用する方が良い場合があります (ツリーを処理する場合、バイナリ ツリーを移動する場合など)。私にとって、ループを使用することが再帰よりも複雑でなく、はるかに難しい場合は、ループを使用することを好みます。

再帰はより多くのメモリを使用しますが、より明確で読みやすい場合があります。 ループを使用するとパフォーマンスが向上しますが、プログラマ (およびそのパフォーマンス) にとって再帰の方が優れている場合があります。

したがって、結論として、再帰または反復のどちらを使用するかを決定することは、実装したいものと、あなたにとってより重要なもの (読みやすさ、パフォーマンス...) に依存し、再帰または反復を求めることは、エレガンスまたはパフォーマンスを求めるようなものです。 .

例

factorialの次の 2 つの実装を検討してください。

反復:

private int Factorial(int num)
{
    int result = 1;
    if (num <= 1) 
       return result;
    while (num > 1)
    {
        result * = num;
        num--;
    }
    return result;
}

再帰：

private int Factorial(int num)
{
    if (num <= 1) 
        return 1;
    return num * Factorial(num - 1);
}

どちらの方法がより読みやすいですか?

明らかに再帰的なもので、簡単で、最初の試行から記述して正常に実行できます。数学の定義をJava!に変換するだけです。

どちらの方法がより効率的ですか?

たとえばnum = 40、時間の比較は次のとおりです。

long start = System.nanoTime();
int res = Factorial(40);
long end = System.nanoTime();
long elapsed = end - start;
        
System.out.println("Time: " + elapsed);

再帰の場合は2993

反復の場合は2138

もちろん、 が大きいほど差numは大きくなります。

于 2013-03-11T19:24:29.307 に答える
10

再帰はプログラマーがプログラムを理解するのに適していますが、多くの場合、再帰はスタックオーバーフローを引き起こすため、常に反復よりも優先されます。

事実、再帰が問題を解決するための最も効率的なアプローチになることはめったになく、反復はほとんどの場合より効率的です。これは、呼び出しスタックが再帰中に非常に頻繁に使用されるため、通常、再帰呼び出しの作成に関連するオーバーヘッドが増えるためです。
これは、多くのコンピュータープログラミング言語が実際に必要な計算を実行するよりもコールスタックの維持に多くの時間を費やすことを意味します。

再帰は反復よりも多くのメモリを使用しますか？ 一般的に言えば、そうです。これは、コールスタックが広範囲に使用されているためです。

再帰または反復を使用する必要がありますか？

再帰は、実装が簡単であり、通常、反復ソリューションよりも「エレガント」であるという事実から、一般的に使用されます。再帰で行われることはすべて繰り返し行うこともできますが、再帰を使用すると、一般にパフォーマンス上の欠点があることに注意してください。ただし、解決しようとしている問題によっては、パフォーマンスの欠点は非常に重要ではない場合があります。その場合、再帰を使用するのが理にかなっています。再帰を使用すると、他のプログラマーがコードをより簡単に理解できるという追加の利点も得られます。これは常に良いことです。

于 2013-03-11T19:27:12.830 に答える
8

他の回答の修正: 反復は再帰に変換できます (スタック オーバーフローが発生する可能性があることに注意してください)。ただし、すべての再帰を直接反復に変換できるわけではありません。多くの場合、そうでなければスタックに格納されるデータを保持するために、何らかの形式のスクラッチ スペースが必要になります。

どちらを選択するかについては、使用する言語と、再帰的なソリューションを作成する利便性によって異なります。

編集して、「直接」の意味を明確にします。

反復にどのように直接変換できるかに基づいて、再帰には 3 つのタイプがあります。

  • メソッドの最後の操作が再帰呼び出しである最適化可能な末尾呼び出し。これらは直接ループに変換できます。
  • 呼び出し間で情報を保持する必要があるため、末尾呼び出しの最適化が不可能な再帰ですが、スタックは必要ありません。のように表現された階乗fact(N)は古典的な例です: 再帰的な定式化では、最後の演算は再帰呼び出しではなく乗算です。これらのタイプの再帰呼び出しは、末尾呼び出しの最適化可能な形式に簡単に変換でき、そこから反復形式に変換できます (階乗を末尾呼び出しの最適化可能な形式に変換するには、2 引数バージョンを使用する必要がありますfact(n, acc)。ここaccで、 は累積結果です) 。 .
  • 各呼び出しで状態を保持する必要がある再帰。古典的な例は、事前注文ツリーのトラバーサルです。各呼び出しで、親ノードを覚えておく必要があります。これを直接反復に変換する方法はありません。代わりに、各呼び出しからの状態を保持する独自のスタックを構築する必要があります。
于 2013-03-11T19:30:24.093 に答える
1

厳密に言えば、再帰と反復はどちらも同じように強力です。再帰的なソリューションは、スタックを使用した反復ソリューションとして実装できます。逆変換は難しい場合がありますが、最も簡単なのは、呼び出しチェーンを介して状態を渡すことです。

Javaでは、再帰的ソリューションが（ナイーブな）反復的ソリューションよりも優れている状況と、基本的に同等である状況が1つあります。他のほとんどの場合、関数呼び出しのオーバーヘッドが回避されるため、反復ソリューションの方が優れています。

関数が暗黙的にスタックを使用する場合、通常は再帰的なソリューションの方が優れています。深さ優先探索について考えてみましょう。

void walkTree(TreeNode t) {
    doSomething(t);

    if (t.hasLeft()) { walkTree(t.getLeft()); }
    if (t.hasRight()) { walkTree(t.getRight()); }
}

同等の反復ソリューションと比較して

void walkTree(TreeNode t) {
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(t);
    while (!s.empty()) {
        TreeNode t = s.pop();
        doSomething(t);
        if (t.hasLeft()) { s.push(t.getLeft()); }
        if (t.hasRight()) { s.push(t.getRight()); }
    }
}

反復的な場合、Stack<>オブジェクトによって作成されたガベージの料金を支払う必要があります。再帰的な場合は、プロセススタックを使用します。これにより、ガベージが作成されたり、メモリが割り当てられたりすることはありません。再帰的ソリューションはスタックオーバーフローに対して脆弱ですが、そうでない場合はより高速に実行されます。

関数が末尾再帰を使用する場合、JITは再帰的なものを反復的なものに変換するため、2つのソリューションは同等になります。末尾再帰とは、関数が最後にそれ自体を再帰的に呼び出して、コンパイラーが蓄積された状態を無視できるようにすることです。たとえば、リストをトラバースします

void walkList(ListNode n) {
    doSomething(n);
    if (n.hasNext()) { walkList(n.getNext()); }
}

「walkList」は関数で最後に実行されるため、JITはそれを本質的に「n = n.getNext（）;gotobeginning」に変換します。これにより反復解と同等になります。

他のほとんどの状況では、反復ソリューションが優れています。たとえば、幅優先探索を実行する場合は、反復ソリューションでのQueue代わりにを使用Stackしてすぐに機能させることができますが、再帰ソリューションに変換するには、両方の暗黙的なスタックの料金を支払う必要があります。コールスタック、そしてそれでもキューの代金を払います。

于 2013-03-11T19:55:28.553 に答える
0

javaの値渡しメカニズムを思い出すと、オブジェクト参照アドレスまたはプリミティブ型の値のコピーを渡す呼び出しごとに、再帰がより多くのメモリを消費することが理解できます。したがって、再帰呼び出しごとに渡すマッハパラメータは、呼び出しごとに消費するマッハメモリとして使用されますが、ループは簡単に使用できます。しかしもちろん、結果を出すための再帰の助けを借りて、より少ないステップを消費するマージソートやツリーの反復などの「分割統治」アルゴリズムがあることを私たちは知っています。したがって、これらの場合、再帰を使用する方が良いと思います。

于 2013-03-11T20:40:38.523 に答える
0

「再帰は常に反復よりも優れている」というステートメントは誤りです。どちらか一方が他方よりも好ましい場合があります。

特定のケースに依存するため、使用するアルゴリズムの種類について決定的な答えを出すことは困難です。たとえば、フィボナッチ数列の一般的な教科書の再帰ケースは、再帰を使用すると非常に効率が悪いため、その場合は反復を使用することをお勧めします。逆に、ツリーのトラバースは、再帰を使用してより効率的に実装できます。

2 番目の質問に答えるには、はい、反復アルゴリズムは再帰を使用して実装でき、その逆も可能です。

于 2013-03-11T19:32:19.380 に答える
0

通常、再帰メソッドには数行のコードが必要ですが、アルゴリズムについて深く考える必要があります。論理的な間違いを犯した場合、おそらくStackOverflowError.

以下に階乗の 2 つのプログラミング例を示します。

反復:

public int calculateIteractiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    int factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial = factorial * i;
    }
    return factorial;
}

再帰的:

public int calculateRecursiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    return n * calculateRecursiveFactorial(n - 1);
}

コードの行数、複雑さ、明確さ、結束などを常に考慮しながら、提案ごとに異なるアイデアについて熟考することは常に良いことです。

于 2013-03-11T19:46:40.297 に答える
0

とはどういう意味ですか? すべての再帰は繰り返しで実装することもでき、その逆も可能です。再帰の方が理解しやすい場合があります。ただし、再帰はスタックを膨張させるため、多くのネストされた呼び出しがメモリ不足の例外を引き起こす可能性があります。その場合、再帰は明らかに最良の選択ではありません。

于 2013-03-11T19:23:13.460 に答える