Velocity Reviews > Somple Recursion Question

# Somple Recursion Question

Johnny Shih
Guest
Posts: n/a

 10-27-2003
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.

Thanks alot,
Johnny

Charles Harrison Caudill
Guest
Posts: n/a

 10-27-2003
Johnny Shih <(E-Mail Removed)> 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.

> 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
Guest
Posts: n/a

 10-27-2003
Thanks guys.

Charles Harrison Caudill wrote:

> Johnny Shih <(E-Mail Removed)> 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.

>
>

>
>
>>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
Guest
Posts: n/a

 10-27-2003
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
Guest
Posts: n/a

 10-27-2003
On 2003-10-27, Johnny Shih <(E-Mail Removed)> 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.
>

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

osmium
Guest
Posts: n/a

 10-27-2003
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.