Having trouble understanding how this recursive function works.

``````int F( int X )
{
return (X<=0) ? 3 : F(X/2)+F(X-3);
}``````

I understand the first part, give it a value 0 or less, get back 3, fine. But greater values I don't understand 2 returns 9, 3 returns 9, 4 returns 15. How?

3
Contributors
4
Replies
5
Views
9 Years
Discussion Span
Last Post by Gagless

Having trouble understanding how this recursive function works.

``````int F( int X )
{
return (X<=0) ? 3 : F(X/2)+F(X-3);
}``````

I understand the first part, give it a value 0 or less, get back 3, fine. But greater values I don't understand 2 returns 9, 3 returns 9, 4 returns 15. How?

It's equivalent to this function. Not sure if that's what your question is.

``````int F( int X )
{
if (X <= 0)
return 3;
else
return F(X/2) + F(X-3);
}``````

I'm aware of how the trinary operator works, its what's going on in the function that has me stumped. After it checks the value to see if its lets than or equal to zero, what is it doing afterwards to return a value?

Given: x == 2 or F(2)
I'll rewrite it as
(F(1) + F(-1))
which I'll rewrite as
((F(0) + F(-2)) + 3)
which I'll rewrite as
((3 + 3) + 3)
which is 9

Given x == 3 or F(3)
OR
(F(1) + F(0))
OR
((F(0) + F(-2)) + 3)
OR
((3 + 3) + 3)
which is 9

You can work out x == 4 on your own. There are a few more nested () but it's not that hard to do.

I get it. Thanks, Lerner.