再帰関数をより速く実行する方法

Question

フィボナッチの6番目のフィボナッチ数を求める必要があります。 fib（6）はfib（4）とfib（5）を最初に呼び出すfib（5）と言う。 fib（5）はfib（4）とfib（3）を呼び出し、最後に基底caseとfib（2）、fib（3）fib（4）、そしてfib fib（5）計算されたfib（6）がfib（4）を呼び出します。今回は同じプロセスf（2）f（3）、最後にf（4）が計算されます。しかし、fiv（5）が呼び出されたときにfiv（4）の値を保存できれば、fiv（4）が呼び出されたときに再度計算する必要はありません。代わりに、fiv（5）が呼び出されたときにfiv（4）に保存された値を使用できます。どのように私は

​​

Answer 1

は、あなたが探している用語であることを行うことができます "memoization。"これは非常に標準的な最適化であり、フィボナッチシーケンスは文字通りテキストブックの例です。

Answer 2

John Zwinckが指摘したように、用語はmemoizationです。つまり、すべてのステップで、計算される中間値を格納しています（再帰呼び出しが高価なため）。

コードは以下のように変更検討：このコードで

#include <iostream> 
using namespace std; 

int main() 
{ 
    int fibboA[10]; 
    fibboA[0]=0;     //1st Fibonacci number is always 0; 
    fibboA[1]=1;     //2nd Fibonacci number is always 1; 

    cout<<fibboA[0]<<"\t"<<fibboA[1]<<"\t"; 

    //3rd onwards, it is the sum of the previous 2; 
    for(int i=2;i<10;i++) 
    { 
     fibboA[i]=fibboA[i-1]+fibboA[i-2]; 
     cout<<fibboA[i]<<"\t"; 
    } 

    return 0; 
} 

、我々は配列fibboA[]に前の値を保存していると計算しながら、以前に記憶された最新の二つの値（i-1番目とi-2番目）を用い現在のフィボナッチ数（i）。

希望すると便利です。

Answer 3

一度に2つのフィボナッチ数を計算することで、単純で効率的な（線形時間）再帰的解を得ることができます。

void fib(int n, int& f1, int& f0) 
{ 
    if (n == 1) 
    { f1= 1; f0= 0; } 
    else 
    { fib(n - 1, f0, f1); f1+= f0; } 
} 

機能はFnとFn-1両方を返します。引数の入れ替えに注目してください。

Answer 4

#include <iostream> 
using namespace std; 
int ar[20]; 
int fib (int n) 
{ 
    if(n==0||n==1) 
     return n; 
    if(ar[n]!=-1)//check if ar[n] exists than just return values 
     return ar[n]; 
    else 
    { 
     ar[n]= fib(n-1)+ fib(n-2); 
     return ar[n]; 
    } 
} 
int main() 
{ 
    for(int i=0;i<20;i++) 
     ar[i]=-1;//initialise all to empty 
    cout<<fib(8); 
} 

Answer 5

ここでは、再帰的な動的なプログラミングソリューションの1つの以上の例です：

#include <vector> 
#include <iostream> 

int fib(int n, std::vector<int>& data) { 
    if (n >= 2) { 
    int& num = data[n - 2]; 
    if (num) { 
     return num; 
    } 
    return (num = fib(n - 1, data) + fib(n - 2, data)); 
    } 
    return n; 
} 

int fib(int n) { 
    if (n >= 2) { 
    std::vector<int> data(n - 1, 0); 
    return fib(n, data); 
    } 
    return n; 
} 

int main(int argc, char *argv[]) { 
    std::cout << fib(23) << std::endl; 
    return 0; 
}