18

classこれら2つの方法を使用した次のサンプルがあります。

プロセス.java:

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        System.out.println("countRecursive: " + num++);
        if (num <= 10) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do System.out.println("countWhile: " + num++);
        while (num <= 10);
    }

}

メインクラス:

public static void main(String[] args) {        

    Process.countRecursive(0);
    Process.countWhile(0);

}

出力：

countRecursive: 0
countRecursive: 1
countRecursive: 2
countRecursive: 3
countRecursive: 4
countRecursive: 5
countRecursive: 6
countRecursive: 7
countRecursive: 8
countRecursive: 9
countRecursive: 10

countWhile: 0
countWhile: 1
countWhile: 2
countWhile: 3
countWhile: 4
countWhile: 5
countWhile: 6
countWhile: 7
countWhile: 8
countWhile: 9
countWhile: 10

しかし、どの「テクニック」の使用が推奨されているのか、その理由を知りたいのです。

前もって感謝します。

4

8 に答える 8

35

メソッド呼び出しのオーバーヘッドと呼び出しスタックの使用により、再帰は遅くなります。

Java は末尾呼び出しの最適化も実行していないため、当てにしないでください。(JVM には、Clojure や Kotlin など、テール コールの最適化を行う言語があります)

もう 1 つの欠点はStackOverflowError、スタックがいっぱいになった場合のリスクです。

試しにこれを行う場合は、Java JDK にある VisualVM を使用することをお勧めします。これは、この種の状況のベンチマークに使用できるプロファイラーです (または、OSS を使用している場合は、オープン ソースの YourKit ライセンスを要求できます)。

単に派手にするために再帰を使用することはお勧めしないことに注意してください。本当に必要な場合に使用します (たとえば、ツリーをトラバースする場合)。

于 2012-12-19T15:56:12.367 に答える
11

時間測定を使用してコードを実行する必要があります。ここに、100 回の再帰/100 回の while ループの出力があります。

Recursive time: 90941
While time: 5180

これは、while ループが再帰よりも高速であることを明確に示しています。

次のコードを実行して、測定値を確認できます。

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        num++;
        if (num <= 100) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do
            num++;
        while (num <= 100);
    }

    public static void main(String[] args) {
        Long start = System.nanoTime();        
        Process.countRecursive(0);
        System.out.println("Recursive time: " + (System.nanoTime() - start));
        Long startWhile = System.nanoTime();
        Process.countWhile(0);
        System.out.println("While time: " + (System.nanoTime() - startWhile));

    }

}
于 2012-12-19T17:08:16.990 に答える
10

各再帰はスタックに格納されるため、再帰の使用はお勧めしません。したがって、再帰呼び出しごとにメソッドパラメーター、ローカル変数などを保存して、その呼び出し前のメソッドの状態を維持する必要があります。

また、この種の問題で再帰を使用しないことは明らかです。それらを使用せざるを得ない場合にのみ、特定のタスクのために残しておく必要があります。

さらに、コードをベンチマークして、どちらがより速く実行されるかを確認することもできます。あなたはアイデアを得るでしょう。

于 2012-12-19T15:57:51.990 に答える
7

再帰呼び出しは、スタック フレームを呼び出しスタックに追加します。ループはしません。再帰が分割統治のようなアルゴリズムの一部でない限り、ループは一般に再帰よりも高速です(あなたの例はそうではありません)。

各メソッドの実行時間を計り、一方が他方よりどれだけ速いかを調べることができるはずです。

于 2012-12-19T15:57:42.553 に答える
6

一般に、次の理由から、再帰よりも反復 (while または for ループなど) を好みます。

  • 反復はより簡単です
  • 再帰が深すぎると、stackoverflow 例外が発生する可能性があります。これは反復では起こりません。
于 2012-12-19T15:58:22.477 に答える
6

一般に、再帰は可能であればループに最適化されます。つまり、スタック フレームの割り当てやスタック フレームのオーバーフローなど、さまざまな理由から、2 つのソリューションが等しい場合は、再帰よりも反復の方が有利です。Tail Recursionを参照してください
。したがって、Java が Tail Recursion を最適化しないという事実を無視すると、ループはより高速になるはずです。

こちらもご覧ください

于 2012-12-19T15:59:27.363 に答える
5

Java では、再帰は、新しいスタック フレームの割り当てを必要とするため、while ループに比べて少しコストがかかります。代替手段がスタックを明示的に管理することである場合、再帰はより高速になる可能性があります

于 2012-12-19T15:57:08.090 に答える
3

他のみんなが言ったことは本当です。もう1つ追加したいのは、あなたが投稿した問題について、1から10まで数えて、再帰または反復を使用しても問題ありません。どちらも実行にかかる時間はごくわずかだからです。一般に、最新のコンピューター システムでは、メモリが非常に安価であり、CPU が非常に強力であるため、プロセスが完了するまでにかかる時間をあまり気にする必要はありません (大規模なデータ セットを扱っている場合を除きます)。

通常、適切なプログラミング手法を使用して、最初は最も快適に感じる方法でプログラムを作成します。その後の実行に時間がかかりすぎる場合は、最適化します。

このレベルで反復と再帰がどのように比較されるかを調べることは悪いことではありません。繰り返しますが、通常は再帰よりも反復の方が適しています。私のポイントは、学ぶべき教訓は、コードをすばやく実行する方法がありますが、小さなデータセットを操作している場合は、多くの場合、それらについて心配する必要がないということです:)

于 2012-12-19T23:44:05.733 に答える