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?
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 ?
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.