如何使递归函数执行得更快

Question

我必须在斐波那契数列中找到第6个斐波那契数。fib（6）首先调用fib（4）和fib（5）来调用fib（5）。fib（5）调用fib（4）和fib（3）并最终到达基本情况，并计算出fib（2），fib（3）fib（4）和最终fib（5）。计算fib（5）时，fib（6）调用fib（4）。这次通过相同的过程f（2）f（3），最后计算出f（4）。但是，如果在调用fiv（5）时可以为fiv（4）保存值，则在调用fiv（4）时无需再次计算。相反，当调用fiv（5）时，我们可以将保存的值用于fiv（4）。我怎样才能做到这一点

int fib(int n)
{
    if(n==0)
         return 0;
    else if(n==1)
            return 1;
    return fib(n-1)+fib(n-2);
}

Answer 1

As John Zwinck has pointed out, the term is memoization. What it means is, in every step, we are storing the intermediate values that are calculated (because the recursive calls are expensive).

Consider your code modified as below:

#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;
}

In this code, we are storing the previous values in the array fibboA[] and using the previously stored latest two values (i-1th and i-2th) while calculating the current fibonacci number (i).

Hope this is helpful.