再帰アルゴリズムと最適化アルゴリズムの比較

以前、「【インタビュー】 - 低速反応再帰」で 3 つの再帰アルゴリズムを読みました。フィボナッチ数列の最適化後のアルゴリズムのアイデアは確かに優れていますが、最後の 2 つの数列に再帰を使用する場合、個人的には労力に見合わないと感じています。再帰を回避できる場合は、再帰を使用しないようにしてください。一部のアルゴリズムは数学を使用して完全に解決できるためです。したがって、この論文では、これら 3 つのシリーズの最終的なアルゴリズムを次のようにまとめています。

1. 配列 1,1,2,3,5,8,13... の 30 番目のビットの値を計算します。

再帰アルゴリズムは次のとおりです。

パブリック静的 int CalculateFibonacciSequence(int インデックス)
        {
            （インデックス< = 0）の場合
            {
                0を返します。
            } 
 
            if (インデックス== 1 ||インデックス== 2)
            {
                1 を返します。
            } 
 
            CalculateFibonacciSequence(インデックス - 1) + CalculateFibonacciSequence(インデックス - 2) を返します。
        }

再帰アルゴリズムを使用して計算する場合、繰り返し操作が多くなります。配列を使用すると、比較的効率的です。最終的なアルゴリズムは次のようになります。

パブリック静的 int CalculateFibonacciSequence(int インデックス)
        {
            （インデックス< = 0）の場合
            {
                0を返します。
            } 
 
            if (インデックス== 1 ||インデックス== 2)
            {
                1 を返します。
            } 
 
            int[] fibonacciArray =新しいint[インデックス];
            フィボナッチ配列[0] = 1;
            フィボナッチ配列[1] = 1; 
 
            (int innerIndex = 2 ; innerIndex <   fibonacciArray.Length ; innerIndex++) フィボナッチ配列の長さ; innerIndex++)
            {
                fibonacciArray[innerIndex] = fibonacciArray[innerIndex - 1] + fibonacciArray[innerIndex - 2];
            } 
 
            fibonacciArray[インデックス - 1]を返します。
        }

フィボナッチ数列の場合、一般式は Fn=F(n-1)+F(n-2)(n>=2, n∈N*) であり、計算を 1 回ループするだけで必要な値が得られます。

2. 1+2+3+4+...+nの値を計算する

再帰アルゴリズムは次のとおりです。

パブリック静的 int CalculateNumberSequenceCount(int インデックス)
        {
            （インデックス< = 0）の場合
            {
                0を返します。
            } 
 
            CalculateNumberSequenceCount(インデックス - 1) + インデックスを返します。
        }

数値 (インデックス) が非常に大きい場合、上記の再帰アルゴリズムでは間違いなく問題が発生します。以下に示す最終的なアルゴリズムを見てみましょう。

パブリック静的 int CalculateNumberSequenceCount(int インデックス)
        {
            （インデックス< = 0）の場合
            {
                0を返します。
            } 
 
            インデックス * (インデックス + 1) / 2 を返します。
        }

1+2+3+4+...+n は、高校数学の等差数列の和の完全に特殊なケースです。 1+2+3+4+......+n は (最初の項 + 最後の項)*項の数/2 に等しいので、結果は n(n+1)/2 になります。これは再帰なしでも解くことができ、式を適用するだけです。

3. 1-2+3-4+5-6+7+...+nの値を計算します。

再帰アルゴリズムは次のとおりです。

パブリック静的 int CalculateNumberSequence(int インデックス)
        {
            （インデックス< =0）の場合
            {
                0を返します。
            } 
 
            インデックス % 2 == 0 を返します。CalculateNumberSequence(index - 1) - index : CalculateNumberSequence(index - 1) + index;
        }

1-2+3-4+5-6+7+...+n の場合、次の 2 つのケースに分けられます。

(1) nが偶数のとき、1-2+3-4+5-6+7+...+n=(1-2)+(3-4)+(5-6)+...+[(n-1)-n]

=-1×(n/2)

=-n/2

（２）ｎが奇数のとき、１−２＋３−４＋５−６＋７＋...＋ｎ＝（１−２）＋（３−４）＋（５−６）＋...＋[（ｎ−２）−（ｎ−１）]＋ｎ

=-1×(n-1)/2 +n

=(n+1)/2

したがって、最終的なアルゴリズムは次のようになります。

パブリック静的 int CalculateCrossNumberSequence(int インデックス)
        {
            （インデックス< =0）の場合
            {
                0を返します。
            } 
 
            インデックス % 2 == 0 を返します。-インデックス / 2 : (インデックス + 1) / 2;
        }

数学的に解決できる問題の場合は、再帰を使用して計算しないようにしてください。もちろん、多くの場合、再帰は依然として必要です。これは再帰アルゴリズムが悪いと言っているのではなく、特定の問題を解決するために最善の方法を使用することが最終的な解決策であるということです。これがお役に立てば幸いです。

オリジナル: http://www.cnblogs.com/jasenkin/archive/2012/02/22/recursion_math_algorithm_comparion.html

【編集者のおすすめ】

1. マット・カッツのブログ記事: Google のアルゴリズムの 10 のベストな調整
2. 簡単なアルゴリズムからアセンブリ言語の予備的研究
3. アルゴリズム学習のための動的プログラミング戦略の紹介
4. 百度、検索エンジンアルゴリズムを調整して微博コンテンツのインデックスを強化
5. 過去10年間のGoogleアルゴリズムの変化