Results 1 to 7 of 7
  1. #1
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default rewriting a recursive function

    Hello, I have to rewrite a recursive function that take a number and raises it to a power. It's sounds simple, but we have to do it in Logn time using X^2n = X^n times X^n. I am having a hard time implementing this. Here is the code for the other power function that I have to modify.

    Java Code:
    public static double pow(double x, int n )
    {
    
    if(x == 0 && n <= 0)
         throw new IllegalArgumentException("Wrong inputs");
    else if (x == 0)
          return 0;
    else if (n == 0)
          return 1;
    else if (n > 0)
          return x * pow(x, n-1);
    else
         return 1/pow(x,-n);
    }
    I am able to follow the recursive calls for this method fine, I just don't know how to implement that weird form I was given to use. Thanks for any help.

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default Re: rewriting a recursive function

    Java Code:
    else if (n > 0)
          return x * pow(x, n-1);
    The idea seems to be that you keep subtracting 1 from n until it becomes small (zero or one).

    I think what you are asked to do is divide n by 2 instead of subtracting one. There is a small complication to deal with if n is odd. But even that shouldn't be too difficult since, in that case, n-1 is even.

  3. #3
    jlczuk is offline Senior Member
    Join Date
    Apr 2012
    Location
    New York State of Confusion, USA
    Posts
    137
    Blog Entries
    1
    Rep Power
    0

    Default Re: rewriting a recursive function

    Here's the deal. The original algorithm will work just fine for solving x^cn where c is some constant such as -2, 3, 21, etc. It will just take longer than if you take advantage of the algebraic rule that x^cn = (x^c)^n. Note that x^cn does NOT equal x^c * x^n

    The original algorithm requires (c*n)-1 passes to achieve the answer. Taking advantage of factoring the exponents will take (n-1)+(c-1) passes.

    I think I have that correct upon re-reading it before posting.

  4. #4
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: rewriting a recursive function

    Quote Originally Posted by pbrockway2 View Post
    Java Code:
    else if (n > 0)
          return x * pow(x, n-1);
    The idea seems to be that you keep subtracting 1 from n until it becomes small (zero or one).

    I think what you are asked to do is divide n by 2 instead of subtracting one. There is a small complication to deal with if n is odd. But even that shouldn't be too difficult since, in that case, n-1 is even.
    Would the modification involve adding another base case? Why would it being odd matter?

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,523
    Blog Entries
    7
    Rep Power
    20

    Default Re: rewriting a recursive function

    Write down the recurrence relations for the pow operator:

    1) x^0 == 1
    2) x^1 == x
    3) x^n == x^(n/2)*x^(n/2) if n is even
    4) x^n == x*x^(n/2)*x^(n/2) if n is odd

    cases 1) and 2) are the sentinel cases while case 3) and 4) describe the recursive step.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: rewriting a recursive function

    Quote Originally Posted by JosAH View Post
    Write down the recurrence relations for the pow operator:

    1) x^0 == 1
    2) x^1 == x
    3) x^n == x^(n/2)*x^(n/2) if n is even
    4) x^n == x*x^(n/2)*x^(n/2) if n is odd

    cases 1) and 2) are the sentinel cases while case 3) and 4) describe the recursive step.

    kind regards,

    Jos
    Thank you very much. I was able to solve it. Now I just have to write it nonRecursively.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,523
    Blog Entries
    7
    Rep Power
    20

    Default Re: rewriting a recursive function

    Quote Originally Posted by Wnt2bsleepin View Post
    Thank you very much. I was able to solve it. Now I just have to write it nonRecursively.
    Think of the exponent n as a binary number; each bit represents a power of the number x: x^1, x^2, x^3, x^4 etc. If a bit in that number n is 1, multiply your result by the corresponding power of x.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Recursive function to iteractive function
    By mikeZet in forum New To Java
    Replies: 0
    Last Post: 03-13-2012, 01:42 AM
  2. Time a recursive function
    By überfuzz in forum New To Java
    Replies: 1
    Last Post: 03-25-2011, 08:27 AM
  3. recursive function
    By jayden in forum New To Java
    Replies: 11
    Last Post: 09-02-2010, 03:00 PM
  4. Help with recursive function in java
    By cachi in forum Advanced Java
    Replies: 2
    Last Post: 07-31-2007, 06:51 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •