converting recursive function to iterative

Discussion in 'C Programming' started by V, May 11, 2008.

  1. V

    V Guest

    Hello:

    Consider the following recursive function:

    inline u64 multiplyPower(u64 V, u8 i, u64 c)
    {
    if (i == 0)
    return V;
    else
    return mul( multiplyPower(V,i-1,c) , c);
    }

    where mul is defined as:
    inline u64 mul(u64 V, u64 c)
    {
    if ((V & 0x8000000000000000 ))
    return (V<<1) ^ c;
    else
    return V<<1;
    }

    I would like to convert the recursive function multiplyPower() to an
    iterative one. Does it look possible? Can some one please help.
    Thanks!
     
    V, May 11, 2008
    #1
    1. Advertising

  2. On 11 May, 12:21, V <> wrote:
    > Hello:
    >
    > Consider the following recursive function:
    >
    > inline u64 multiplyPower(u64 V, u8 i, u64 c)
    > {
    > if (i == 0)
    > return V;
    > else
    > return mul( multiplyPower(V,i-1,c) , c);
    >
    > }
    >
    > where mul is defined as:
    > inline u64 mul(u64 V, u64 c)
    > {
    > if ((V & 0x8000000000000000 ))
    > return (V<<1) ^ c;
    > else
    > return V<<1;
    >
    > }
    >
    > I would like to convert the recursive function multiplyPower() to an
    > iterative one. Does it look possible? Can some one please help.


    Yes it is possible and quite easy. I am however reluctant
    to provide you with a complete answer since this looks
    like homework. I will try to give you some hints although
    I think it will be hard finding the middle point between
    trivial (hence unhelpful) hints and a complete solution.

    First, the code for mul is irrelevant. As long as you know
    the return type, that's all you need to turn the recursion
    into a loop. Second, try working out on a piece of paper
    the symbolic result of multiplyPower for small functions
    of i and see if that gives you a hint.

    For example
    i=0 multiplyPower returns V
    i=1 multiplyPower returns mul(V,c)
     
    Spiros Bousbouras, May 11, 2008
    #2
    1. Advertising

  3. V

    V Guest

    Following is what I can think of...but it doesn't seem to be working ;-
    ( Any pointers...Thanks!

    inline u64 multiplyPower_iter (u64 V, u8 i, u64 c)
    {
    u64 result=1;
    int j;

    if ((i == 0))
    return V;
    else
    {
    {
    while (i--)
    {
    result *= 2;
    }

    result *= mul (V,c);
    }
    return result;
    }
    }
     
    V, May 13, 2008
    #3
  4. V

    V Guest

    Mistyped one thing (shown as CORRECTION below)...but still doesn't
    work ;-(

    n May 12, 6:54 pm, V <> wrote:
    > Following is what I can think of...but it doesn't seem to be working ;-
    > ( Any pointers...Thanks!
    >
    > inline u64 multiplyPower_iter (u64 V, u8 i, u64 c)
    > {
    > u64 result=1;
    > int j;
    >
    > if ((i == 0))
    > return V;
    > else
    > {
    > {

    CORRECTION----> i--;
    > while (i--)
    > {
    > result *= 2;
    > }
    >
    > result *= mul (V,c);
    > }
    > return result;
    > }
    >
    > }
     
    V, May 13, 2008
    #4
  5. V <> writes:

    > Mistyped one thing (shown as CORRECTION below)...but still doesn't
    > work ;-(


    Did you follow Spiros Bousbouras advice?

    The recursive version does this:

    i=0 return V
    i=1 return mul(mp(V,0,c),c) i.e. mul(V,c)
    i=2 return mul(mp(V,1,c),c) i.e. mul(mul(V,c),c)
    i=3 return mul(mp(V,2,c),c) i.e. mul(mul(mul(V,c),c),c),c)

    You need to repeatedly apply mul to V which is not what your code
    does.

    --
    Ben.
     
    Ben Bacarisse, May 13, 2008
    #5
    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. Tuurbo46

    iterative structue

    Tuurbo46, Oct 5, 2005, in forum: Java
    Replies:
    0
    Views:
    620
    Tuurbo46
    Oct 5, 2005
  2. BQ
    Replies:
    14
    Views:
    758
    Richard Bos
    Mar 25, 2005
  3. n00m
    Replies:
    12
    Views:
    1,115
  4. Baba
    Replies:
    42
    Views:
    2,393
  5. Ania
    Replies:
    15
    Views:
    724
Loading...

Share This Page