CODEWITHSUNDEEP
c++crecursionfibonacci
pexea12
pexea12

Reputation: 1209

Get a faster code in recursion algorithm

I am learning about recursion in C. My problem is: Print 80 first Fibonacci numbers (using recursion)

Here is the book's 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 runs 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 you.

Upvotes: 4

Views: 745

Answers (4)

James Kanze
James Kanze

Reputation: 153919

The algorithm is caching previously calculated values in the array f. This array is initialized with 0 (since it is static). The test you mention removing checks if there is a cached value, and returns it. By eliminating the test, you never use the cached value, but recalculate it every time. And that is expensive, since you end up calculating the same value many, many times.

EDIT:

I might add that if this is code from a book, you should get a different book, because it is very poor style. In C, I'd write something like:

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

You'll notice that the code is actually a lot simpler this way.

In C++, of course, I'd use std::vector for the cache, so I don't have some hidden, hard-coded limit. (For that matter, in C, I'd probably implement something similar, to avoid the hard-coded limit. But I wouldn't expect that in a pedagogic example.)

Upvotes: 5

antonpuz
antonpuz

Reputation: 3316

This ideas of solving problem is called dynamic programming, this particular method is called memorization:

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

The idea is to store previously calculated values and use them instead of calculating them again. in your case they are stored in: f[100] and once they are calculated once a fibonacci number will never be recalculated. when you delete the assignment you disable this storage and the values are recalculated each time.

Upvotes: 1

Abhishek Gupta
Abhishek Gupta

Reputation: 1337

At First if you use the naïve formula for recursion ( i.e if you comment the line 10 in your code)

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

Fib Recursion Tree

As you can see it computes many values more than once(ans hence is inefficient ) , or in other words have exponential time complexity as every node resolves into 2 branches ( O(2^n) )

So if he save our work and use it to solve the same problem when occurred again: We can achieve linear time complexity ( O(n) )

In your code the array f is cache Fib Recursion tree with Memoization

However if you interested to know(although it is not asked in question) , you can calculate Fib(n) or any linear recurrence relation in general faster than this , in logarithmic time complexity via Matrix Exponention. ( O(logN) )

Upvotes: 9

Laszlo Fuleki
Laszlo Fuleki

Reputation: 342

That is because the cached results aren't being used anymore in that way. You see, when you use recursive functions such as these for instance f(20) gets called multiple times, try to draw the call tree on a paper and you'll see. What that line does is essentially avoiding recalculation of these values (memoization, if you want to put it in that way).

Upvotes: 1

Related Questions