Somple Recursion Question

Discussion in 'C Programming' started by Johnny Shih, Oct 27, 2003.

  1. Johnny Shih

    Johnny Shih Guest

    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
     
    Johnny Shih, Oct 27, 2003
    #1
    1. Advertising

  2. 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.


    > 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
     
    Charles Harrison Caudill, Oct 27, 2003
    #2
    1. Advertising

  3. Johnny Shih

    Johnny Shih Guest

    Thanks guys.

    Charles Harrison Caudill wrote:

    > 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.

    >
    >
    >>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
    >
     
    Johnny Shih, Oct 27, 2003
    #3
  4. 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
     
    Martin Ambuhl, Oct 27, 2003
    #4
  5. Johnny Shih

    James Hu Guest

    On 2003-10-27, 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.
    >
    > 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
     
    James Hu, Oct 27, 2003
    #5
  6. Johnny Shih

    osmium Guest

    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.
     
    osmium, Oct 27, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roedy Green

    recursion : moron-level question

    Roedy Green, Jul 4, 2004, in forum: Java
    Replies:
    13
    Views:
    615
    Mark McConnell
    Jul 8, 2004
  2. Replies:
    12
    Views:
    624
    Virgil Green
    Aug 29, 2005
  3. da Vinci
    Replies:
    12
    Views:
    560
    Alan Morgan
    Oct 28, 2003
  4. JustSomeGuy
    Replies:
    9
    Views:
    331
    Victor Bazarov
    Nov 18, 2004
  5. Replies:
    8
    Views:
    751
    John Reye
    Apr 26, 2012
Loading...

Share This Page