24

iterationとと の違いは何ですか?recursionなぜ/いつの方が良いですか:

while (true) {
    // Iterating
}

と

private void recursion() {
    if (true)
        recursion(); // Recursing

    return;
}

recursive単純なループで簡単に実行できる実装がたくさんあります。

4

8 に答える 8

36

再帰と同じアルゴリズムの反復バージョンには 2 つの主な違いがあります。

まず第一に、反復アルゴリズムよりも再帰アルゴリズムを理解する方がほとんど良い場合があります (少なくとも経験豊富なプログラマーの場合)。したがって、表現力が向上し、場合によっては読みやすさが向上します (他の場合では正反対の結果になる可能性もあります)。 )

表現力はプログラミング言語にとって大きな問題であり、同じコードを 20 行ではなく 5 行で記述できることは大きな問題です。

欠点として、コードのパフォーマンスが低下します。再帰関数は、関数レコードをメモリに保持し、あるメモリ アドレスから別のメモリ アドレスにジャンプして、パラメーターを渡して値を返す必要があります。そのため、パフォーマンスが非常に悪くなります。

まとめ:

反復アルゴリズム = パフォーマンスは高速ですが、書きにくい (読みにくい場合もあります)

再帰的アルゴリズム = 書き込みは速いが、パフォーマンスが悪い (理解しやすい場合もある)

次の例を見てください。

public static long fib(long n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

対

    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        long prev = 1, current = 1, next = 0;
        for (long i = 3; i <= n; i++) {
            next = prev + current;
            prev = current;
            current = next;
        }
        return next;
    }

ソース：

http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java

于 2013-11-05T17:19:37.570 に答える
1

それらは同じことを行うための異なる方法です。すべての再帰的実装は、1 つ (または複数) のループで実行でき、その逆も可能です。それは、その背後にあるロジック、それについて考える方法に関するものです。階乗は最良の例ではありませんが、n * (n-1)!再帰的に使用することは理にかなっています。

于 2013-11-05T17:14:49.177 に答える
0

それらは、さまざまな問題を解決するために交換可能に使用できます。本質的に、再帰関数を反復的に記述でき、その逆も可能です。

反復により、プログラムのパフォーマンスが向上する場合があります。一方、再帰はより直感的で洗練された結果をもたらす場合があります。お好みに合わせてどちらかお選びいただけます！

于 2013-11-05T17:20:54.353 に答える
0

再帰関数は、条件が満たされるまで自分自身を呼び出すプロセスを実行しますが、反復はループ制御構造 (while、do while、for など) を使用して、特定の条件が満たされるまでコードのセクションを繰り返します。

再帰的な例:

int rec_func(int u, int k) {
  if (k == 0)
    return u;
  return rec_func(u * k, k - 1);
}

繰り返しの例:

int ite_func(int u, int k) {
  while (k != 0) {
    u = u * k;
    k = k - 1;
  }
  return u;
}

それらの間の唯一の本当の違い IMO は、コンパイルの違いです。

于 2013-11-05T17:21:44.527 に答える
0

再帰と反復は、ソリューションについて考える別の方法です。その違いを完全な範囲で詳細に説明することは困難です。サンプル コードでは、すでに違いを示しています。再帰関数はそれ自体を呼び出す関数ですが、反復関数はコードのブロックをループする関数です。それらをよりよく理解するのに役立ついくつかの記事を次に示し ます。

イテレーション ウィキ

CodeProject SO #1

そう #2

于 2013-11-05T17:20:04.487 に答える