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]

Re: Somple Recursion Question

Johnny Shih writes:
[color=blue]
> 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[/color]
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]

Re: Somple Recursion Question

Johnny Shih <awei29@hotmail .com> wrote:[color=blue]
> Hi guys,[/color]
[color=blue]
> I am having to figure out the recusion in this function.[/color]
[color=blue]
> 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;
> }[/color]

[color=blue]
> recfn(7) gives me 11
> I am not able to figure out the steps and numbers that got added up to that.[/color]
[color=blue]
> Please help.[/color]
[color=blue]
> Thanks alot,
> Johnny[/color]


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]

Re: Somple Recursion Question

Thanks guys.

Charles Harrison Caudill wrote:
[color=blue]
> Johnny Shih <awei29@hotmail .com> wrote:
>[color=green]
>>Hi guys,[/color]
>
>[color=green]
>>I am having to figure out the recusion in this function.[/color]
>
>[color=green]
>>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;
>>}[/color]
>
>
>[color=green]
>>recfn(7) gives me 11
>>I am not able to figure out the steps and numbers that got added up to that.[/color]
>
>[color=green]
>>Please help.[/color]
>
>[color=green]
>>Thanks alot,
>>Johnny[/color]
>
>
>
> 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
>[/color]

[Martin Ambuhl]

Re: Somple Recursion Question

Johnny Shih wrote:[color=blue]
> 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.[/color]

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]

Re: Somple Recursion Question

On 2003-10-27, Johnny Shih <awei29@hotmail .com> wrote:[color=blue]
> 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.[/color]

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