Recursion/fibonacci

[aluhnev]

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?

[mike_2000_17]

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).

[aluhnev]

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

[sepp2k]

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.

[aluhnev]

How to determine what kind of function it is : is it tail recursive ?