What is a recursion???!

[cozyhozy]

Anyone know how to do this question?
Use recursion to implement the following recurrence relation f(x):
f(x)=1 where =1
f(x) = f((x+1)/2) +1 where x is odd
f(x) = f(x/2) +1 where x is even

This is what i did:

#include<stdio.h>

int func (int x)

int main()
{
int x;
printf("Please enter the value of x: ");
scanf("%d", &x);

int func=func(x);
printf("%d",func) ;

return 0;
}

int func (int x)
{
if(x==1)
return 1;
else if (x%2 ==1)
return func ( (x+1)/2 ) + 1;
else
return func (x/2) + 1;
}

But it doesnt work.
Could you please kindly explain how a recursion work as well?
Thank youuuuu!

[Gaminic]

I'm guessing it continues eternally? Once 'x' hits 2, it will always be 2 (2/2 +1 = 2).
(Solution: check for x == 1 as well as x == 2)

[1vRz3TCk]

I'm guessing it continues eternally? Once 'x' hits 2, it will always be 2 (2/2 +1 = 2).

when x is 2 it will call func() with 2/2, so the guard (x==1) is adequate on its own.

cozyhozy,
What is the problem you are having, Do you not get the result you expect, or does it not compile...

this doesn't look good:

int func=func(x);
printf("%d",func) ;

try changing the name of the variable. int result = func(x); ...

[cozyhozy]

I changed the name of variable. Now it can compile but the outputs are incorrect?
For e.g. when i enter 12, i'm supposed to obtain 7. But the output was 5.
I enter 7, the output was 4 instead of 5.
Or am i missing out something?
Can someone explain to me?
Thanks!!

[helios]

I don't see how you'd get anything other than 5:

f(1)=1
f(x)=if x is odd then f((x+1)/2)+1 else f(x/2)+1

f(12)
(if 12 is odd then f((12+1)/2)+1 else f(12/2)+1)
(f(12/2)+1)
(f(6)+1)
((if 6 is odd then f((6+1)/2)+1 else f(6/2)+1)+1)
((f(6/2)+1)+1)
((f(3)+1)+1)
(((if 3 is odd then f((3+1)/2)+1 else f(3/2)+1)+1)+1)
(((f((3+1)/2)+1)+1)+1)
(((f(4/2)+1)+1)+1)
(((f(2)+1)+1)+1)
((((if 2 is odd then f((2+1)/2)+1 else f(2/2)+1)+1)+1)+1)
((((f(2/2)+1)+1)+1)+1)
((((f(1)+1)+1)+1)+1)
((((1+1)+1)+1)+1)
(((2+1)+1)+1)
((3+1)+1)
(4+1)
5

[1vRz3TCk]

when i enter 12, i'm supposed to obtain 7. But the output was 5.

Is this a test case given to you?

F(12) = F(6)    + 1
F(12) = (F(4)   + 1) + 1
F(12) = ((F(2)  + 1) + 1) + 1
F(12) = (((F(1) + 1) + 1) + 1) + 1
F(12) = (((1)   + 1) + 1) + 1) + 1

[cozyhozy]

Oh i made a huge mistake in calculating.
Thanks people for your clear explanation! :)