Java でアルゴリズムを実装する場合は、再帰に注意してください。

現象：

再帰は、アルゴリズムの原理をうまく説明できる古典的なアルゴリズム実装です。再帰は、アルゴリズムの説明、パフォーマンス、コード構造の理解に適しています。

しかし、この記事で言いたいのは、Java で再帰アルゴリズムを実装するときには、再帰を使用せず、非再帰実装に変換するようにすることです。

最近、より複雑なアルゴリズムを実装する際に試してみたところ、非再帰実装では再帰実装に比べて速度が 1/3 向上することがわかりました。

次の簡単な例を見てみましょう: (注: 説明を簡略化するために、ここでは簡単な例のみを使用しています)

入力パラメータ: N

出力: log1+log2+log3+....+logN

2 つの実装コードは次のとおりです。

Javaコード

パッケージテスト; 
    
公共 クラスRecursiveTest { 
     /**
     * 再帰実装
     *
     * @param n
     * @戻る
     */      
    公共 静的 二重再帰( long n) { 
         (n == 1 )の場合{ 
             Math.log( 1 )を返します。
        }それ以外{ 
             Math.log(n) + recursive(n - 1 )を返します。
        }
    } 
    
     /**
     * 非再帰実装
     *
     * @param n
     * @戻る
     */      
    公共 静的 直接倍精度浮動小数点数型( long n) { 
        ダブル結果 = 0 ; 
         ( int i = 1 ; i <= n; i++)の場合{
            結果 += Math.log(i);
        } 
        結果を返します。
    } 
    
    公共 静的  void main(String[] args) { 
        整数i = 5000000 ; 
        長いテスト = System.nanoTime(); 
        長いstart1 = System.nanoTime(); 
        ダブルr1 = 再帰(i); 
        長いend1 = System.nanoTime(); 
        長いstart2 = System.nanoTime(); 
        ダブルr2 = 直接(i); 
        長いend2 = System.nanoTime(); 
    
        System.out.println( "再帰結果:" + r1);
        System.out.println( "使用された再帰時間: " + (end1 - start1));
        System.out.println( "非再帰結果:" + r2);
        System.out.println( "非再帰使用時間: " + (end2 - start2));
    }
 }

実行結果は次のとおりです。

再帰結果:7.212475098340103E7
再帰使用時間:539457109
非再帰結果:7.212475098340103E7
非再帰使用時間:282479757

再帰実行時間は非再帰実行時間のほぼ 2 倍であることがわかります。

(注: 上記のコードは、パラメータ -Xss200m の下で実行されます。スタック スペースが不足している場合は、直接実行できません)

理由の簡単な分析:

上図は、Java スレッド スタックの構造を示しています。 Java はスレッドごとにスタックを維持し、スタックはメソッドごとにスタック フレームを保存します。スタック フレームはメソッドの実行状態を表します。 これは、メソッド スタックと呼ばれることが多いものです。 ***1つは現在実行中のスタック フレームです。

各メソッド呼び出しには次の内容が含まれます。

1. 新しい呼び出しメソッドのスタックフレームを生成する

2. 現在のメソッドのスタックフレームの状態を保存する

3. スタック フレームのコンテキストが *** メソッド スタック フレームに切り替わります。

再帰的な実装はスタック メモリの消費 (多くの場合、Xss パラメータの調整が必要) とスタック フレームの作成および切り替えによるパフォーマンスのオーバーヘッドにつながり、最終的には効率に大きな影響を与えます。

したがって、アルゴリズムの効率を向上させたい場合は、再帰を使用しないことが基本原則です。

さらに、再帰はアルゴリズムを理解するために使用する方法です。コードに実装すると、基本的に非再帰的なコード実装に変換できます。