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

    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,708
    Rep Power
    13

    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
    4

    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 online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,051
    Blog Entries
    7
    Rep Power
    23

    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
    The only person who got everything done by Friday was Robinson Crusoe.

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

    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 online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,051
    Blog Entries
    7
    Rep Power
    23

    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
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. Recursive function to iteractive function
    By mikeZet in forum New To Java
    Replies: 0
    Last Post: 03-13-2012, 02:42 AM
  2. Time a recursive function
    By überfuzz in forum New To Java
    Replies: 1
    Last Post: 03-25-2011, 09: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
  •