CODEWITHSUNDEEP
c++recursionfibonacci
aJynks
aJynks

Reputation: 689

Recursive Fibonacci .. no idea what is going on

I recently made a code for a procedural function in c++ application for calculating F(n) in Fibonacci sequence.

Anyway, I can not get it to produce the correct result using recursion. For example whenever I enter the value 5, it returns 8, were my other procedural code returns the correct vale of 5.

This is the function I am using... and the code I got from the net. The problem I have is the code from the net and my code are exactly the same (nearly) but BOTH give the wrong value...

http://codepad.org/pMKs4kvb

What is going on?

Upvotes: 0

Views: 243

Answers (3)

Shashank Kadne
Shashank Kadne

Reputation: 8101

I guess you need to add another condition n==2 to your if loop...your program should be...

int FibiRec(int n){
        int result = 0;
        if (n == 0 || n == 1 || n==2){
            return 1;
        }else{
            return FibiRec(n-1) + FibiRec(n-2);
        }
    }

This is because, for n=2, FibiRec(1) and FibiRec(0) will be called , which are your stop conditions....

Upvotes: -1

Tejasva Dhyani
Tejasva Dhyani

Reputation: 1362

your numbering starts from 0...while the procedural numbering starts from 1

n : 0, 1, 2, 3, 4, 5

F(n) : 1, 1, 2, 3, 5, 8

Upvotes: 0

Rohan Prabhu
Rohan Prabhu

Reputation: 7302

Well, simply put, your function is printing out the following series:

1, 1, 2, 3, 5, 8 ...

And hence, F(5) = 8 (if we're talking zero indexed here). If you want the following to be printed:

0, 1, 1, 2, 3, 5, 8 ...

Which is the sequence as recognized by OEIS, then all you need to do is make sure you define F(0) = 0. To that extent, your function should simply be:

int FibiRec(int n) {
    if (n == 0 || n == 1) {
        return n; // IMPORTANT
    } else {
        return FibiRec(n-1) + FibiRec(n-2);
    }
}

At the same time I would like to add: Your function has a horrible time complexity of O(2^n). With your function, try generating the 40th or 100th fibonacci number and you'll realize what I'm talking about.

Upvotes: 3

Related Questions