Big-O time complexity for this recursive Fibonacci?

Question

I have a program that prints Fibonacci Series using Recursion. There are better methods for it, but I was asked to use recursion so i had to do it this way.

Here is the program:

#include <stdio.h>
#define TERMS 10

long fibo(int);

int main(void){
   for(int i = 1; i <= TERMS; i++) {
       printf("%ld", fibo(i));
   }
   return 0;
}

long fibo(int n){
    if (n < 3) {
        return 1;
    }
    else {
        return fibo(n - 1) + fibo(n - 2);
    }
}

I know this is really a bad approach for the Fibonacci Series and this is clear from above as TERMS get to be more than 35, the program takes a lot of time to complete.

I have gone through this answer and could not understand how they solved it but it looks like

Time complexity for fibo(int n) is O(2^n)

Again I maybe completely wrong, but all I want to is :

What is the Time-Complexity for this complete program, Explain briefly how you calculated it?

If you have a better approach for calculating Fibonacci using recursion, it is also welcome.

Answer 1

c(fibo(n)) = c(fibo(n - 1)) + c(fibo(n - 2)) + O(1)

Note that the complexity follows the exact formula as the series since all computational branches always end in leaves valued 1 so the exact (theta) complexity can accurately be computed by the closed formula for the Fibonacci series itself

but that's out of the scope of your question, all we need to note here is that

c(fibo(n)) < 2 * c(fibo(n - 1))

All we need now is to solve the upper bound series defined by

an = 2 * an-1 (a1,2 = 1)

results in

an = 2^n

So, you get the upper O bound you wanted of 2^n.

if you run it several times you will get

sigma(c(fib(n))) from 1 to TERMS = O(2^(TERMS + 1) - 1)

which is a simple mathematical fact, meaning that in your case (TERMS = 10) you get

2^11 - 1 = 2047

---

As for your question regarding a better way to do this recursively...

int fib(int n, int val = 1, int prev = 0)
{
    if (n == 0) {
        return prev;
    }
    if (n == 1) {
        return val;
    }
    return fib(n - 1, val + prev, val);
}

This is what's called a tail recursion and takes O(n) (in fact it can be optimized by a good compiler to be implemented as a loop and will then also use up a constant memory consumption)