4

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.

Improve this question
3
  • 6
    It's called memoization. Commented Jan 7, 2015 at 17:16
  • It looks like a memoization. The function is attributing the first 100 fib numbers as they are calculated and returning prematurely if already memoized. Commented Jan 7, 2015 at 17:16
  • Yeah, I still get the correct answer. What do you mean by "inefficiency"? Commented Jan 7, 2015 at 17:23

4 Answers 4

Reset to default
9

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) )

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

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.)

Improve this answer

2 Comments

Good points on range checking and using a local variable (still with static storage duration). However, the early return in the original code was far simpler than your rewrite, as well as conceptually more straightforward ("if the cache has the value already, we're done" vs "make sure the cache has the value by calculating it if it isn't already in the cache, then return from the cache").
The early return on the same line as the if makes the original completely unreadable; at the very least, it needs to be on a separate line. Otherwise... If you're caching, it's much clearer if you always return the cached value. Recursion in general may be one of the rare cases where a premature return to break the recursion makes sense. I would still avoid it in pedagogical text; 99 times out of 100, premature return signals insufficient thought about the algorithm, and is less clear. (At least assuming that you are handling errors as fatal or with exceptions.)
1

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).

Improve this answer

3 Comments

The results are still being cached. He just doesn't use the cached values.
@JamesKanze: It seems reasonable to say that a write-only memory is not a cache. A log, perhaps.
@BenVoigt Yes and no. The memory is still a cache, in the sense that it could be used if you wanted to. But yes, it doesn't fulfill the purpose of a cache unless it is actually used.
1

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.

Improve this answer

3 Comments

Some may argue the difference between Dynamic Programming and Memoization.
@AbhishekGupta memorization is used by the dynamic programming technique to break into sub problems. the scheme here is dynamic programming scheme which uses memorization to store the results.
Memoization is the particular technique applied here, Dynamic Programming is a broad approach which includes memoization and many other techniques.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.