Get faster code in recursion algorithm

Question

I learn about recursion in C. My problem: print the 80 first Fibonacci numbers (using recursion)

Here is the book code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long f[100];

long long fib(int n)
{
    if (n<2) return 1;
    if (f[n]>0) return f[n];
    f[n] = fib(n-1)+fib(n-2);       
    return f[n];
}
int main()
{
    int i;
    for (i = 0; i<= 80; i++) printf ("%lld \n", fib(i));
    system ("pause");
    return 0;
}

With this code, my program is very fast, and I immediately get 80 Fibonacci numbers.

However, when I delete the 10th line:

if (f[n] > 0) return f[n];

The program becomes very slow, and it takes about 20 seconds to print all 80 numbers. Can anyone explain why? Thank.

Answer 1

First, if you use a naive recursion formula (i.e. if you comment line 10 in your code)

F(n) = F(n-1) + F(n-2)

, ( ) , , , node 2 (O(2^n))

, , : (O(n))

f cache

, ( ), Fib(n) , , Matrix Exponention. (O(logN))

Answer 2

f. 0 ( ). , , . , , . , , .

EDIT:

, , . C - :

long long
fib( int n )
{
    static long long cache[100];    //  limit scope, and give it a good name
    assert( n >= 0 && n < sizeof(cache) / sizeof(cache[0]) );
                                    //  make sure input is legal.
    if ( cache[n] == 0 ) {
        cache[n] = n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 );
    }
    return cache[n];
}

, .

++, , std::vector , , . ( , C, , , - , . .)

Answer 3

, . , , , , f (20) , , . , , , (memoization, ).

Answer 4

, :

http://en.wikipedia.org/wiki/Dynamic_programming

The idea is to save previously calculated values ​​and use them instead of calculating them again. in your case, they are stored in: f[100]and after calculating them, as soon as the Fibonacci number is never recounted. when you delete the assignment, you turn off this storage and the values ​​are recalculated every time.