``````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?

## 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 developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.