Somple Recursion Question

[Johnny Shih]

Hi guys,

I am having to figure out the recusion in this function.

int recfn(int v)
{
if(v==1 || v==0)
return 1;
if(v%2==0)
return recfn(v/2)+2;
else
return recfn(v-1)+3;
}
recfn(7) gives me 11
I am not able to figure out the steps and numbers that got added up to that.

Please help.

Thanks alot,
Johnny

[osmium]

Johnny Shih writes:

I am having to figure out the recusion in this function.

int recfn(int v)
{
if(v==1 || v==0)
return 1;
if(v%2==0)
return recfn(v/2)+2;
else
return recfn(v-1)+3;
}
recfn(7) gives me 11
I am not able to figure out the steps and numbers that got added up to

that.

I think the most informative way to proceed is to add a print statement as
the first statement in the function. Print the value of v. If necessary,
keep adding print statements until it makes sense.

[Charles Harrison Caudill]

Johnny Shih <aw****@hotmail.com> wrote:

Hi guys, I am having to figure out the recusion in this function. int recfn(int v)
{
if(v==1 || v==0)
return 1;
if(v%2==0)
return recfn(v/2)+2;
else
return recfn(v-1)+3;
}
recfn(7) gives me 11
I am not able to figure out the steps and numbers that got added up to that. Please help. Thanks alot,
Johnny

recfn(7) -> 3 + recfn(6)
recfn(6) -> 2 + recfn(3)
recfn(3) -> 3 + recfn(2)
recfn(2) -> 2 + recfn(1)
recfn(1) -> 1

do the math

--
Harrison Caudill | .^ www.hypersphere.org
Computer Science & Physics Double Major | | Me*Me=1
Georgia Institute of Technology | '/ I'm just a normal guy

[Johnny Shih]

Thanks guys.

Charles Harrison Caudill wrote:

Johnny Shih <aw****@hotmail.com> wrote:

Hi guys,

I am having to figure out the recusion in this function.

int recfn(int v)
{
if(v==1 || v==0)
return 1;
if(v%2==0)
return recfn(v/2)+2;
else
return recfn(v-1)+3;
}

recfn(7) gives me 11
I am not able to figure out the steps and numbers that got added up to that.

Please help.

Thanks alot,
Johnny

recfn(7) -> 3 + recfn(6)
recfn(6) -> 2 + recfn(3)
recfn(3) -> 3 + recfn(2)
recfn(2) -> 2 + recfn(1)
recfn(1) -> 1

do the math

[Martin Ambuhl]

Johnny Shih wrote:

Hi guys,

I am having to figure out the recusion in this function.

int recfn(int v)
{
if(v==1 || v==0)
return 1;
if(v%2==0)
return recfn(v/2)+2;
else
return recfn(v-1)+3;
}
recfn(7) gives me 11
I am not able to figure out the steps and numbers that got added up to
that.

recfn(7) = recfn(6) + 3
= recfn(3) + 2 + 3 = recfn(3) + 5
= recfn(2) + 3 + 5 = recfn(2) + 8
= recfn(1) + 2 + 8 = recfn(1) + 10
= 1 + 10 = 11

Now try doing your trivial busywork for yourself

--
Martin Ambuhl

[James Hu]

On 2003-10-27, Johnny Shih <aw****@hotmail.com> wrote:

Hi guys,

I am having to figure out the recusion in this function.

int recfn(int v)
{
if(v==1 || v==0)
return 1;
if(v%2==0)
return recfn(v/2)+2;
else
return recfn(v-1)+3;
}
recfn(7) gives me 11
I am not able to figure out the steps and numbers that got added up to that.

Please help.

Try putting in printf statements.

int recfn(int v)
{
int r;

if(v==1 || v==0) {
r = 1;
} else if(v%2==0) {
r = recfn(v/2)+2;
} else {
r = recfn(v-1)+3;
}

printf("recfn(%d) == %d\n", v, r);
return r;
}

-- James