O time complexity for this recursive Fibonacci?

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.

---

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)

---

Well in general there is math behind it, the Fibonacci is explained there: https://en.wikipedia.org/wiki/Recurrence_relation

If you dont have to prove it and you only have to write it down correctly, you just have to think about how the algorithm behaves and how many repetitions there would be for some number and then you can try to generalize it for any input n .

Paper is your friend!

If you have fibonacci with value "10" in your recursion, you are basically saying (the finonacci for 10 is the fibonacci for 9 + fibonacci for 8)

And then fo fibonacci 9 you say - it is fibonacci 8 + fibonacci 7 etc.

You can draw a graph:

I think it is obvious that it will continue to an almost full binary tree. And you can see that for every level the number of nodes is doubled, therefore for fib(10) it will repeat itself 10 times having at the bottom almost 2^10 , therefore for fib(n) it will be 2^n .

How to make it effective in recursive alghoritm? Well you can see right from the picture that ie fib(7) is solved three times. So you have to remember the fib(n) once you calculated it. It can be a global variable or you can pass reference to an object through the recursive call.

Then you dont just say "fib(n-1) and fib(n-2)", you first look "is fib(n-1) counted"? And if so, instead of doing recursion, use the calculated value.

链接地址: http://www.djcxy.com/p/39920.html

上一篇: O（n）和O（1 + n）之间的实际区别？

下一篇: O递归斐波那契的时间复杂度？