Get a faster code in recursion algorithm

Question

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.

Answer 1

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)

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

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