int Cabin (int n);

int _tmain(int argc, _TCHAR* argv[])
{
    cout << Cabin(8) << endl;
    return 0;
}

int Cabin (int n)
{
        if (n == 1)
            return 0;
    else
            return Cabin(n/2) + 1;
}

Hi ,can someone explain why is the answer 3 here:if to folow the formula the answer is 8,5,3,2,1 and then if to return values,can not be 3,were is my mistake in logic?

Recommended Answers

Well, it's not the Fibonacci sequence at all. I mean, the recursion return Cabin(n/2) + 1; is not at all the Fibonacci recursion. It should be something like return Cabin(n-1) + Cabin(n-2);, but …

Jump to Post

All 4 Replies

Well, it's not the Fibonacci sequence at all. I mean, the recursion return Cabin(n/2) + 1; is not at all the Fibonacci recursion. It should be something like return Cabin(n-1) + Cabin(n-2);, but watch out for the termination condition (not to mention that this is not a very efficient recursion).

ok,i see,but still why is the answer 3?

Cabin(8) = Cabin(8/2) + 1
         = Cabin(4) + 1
         = Cabin(4/2) + 1 + 1
         = Cabin(2) + 1 + 1
         = Cabin(2/2) + 1 + 1 + 1
         = Cabin(1) + 1 + 1 + 1
         = 0 + 1 + 1 + 1
         = 3

That's why the answer is 3.

How to determine what kind of function it is : is it tail recursive ?
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.