Results 1 to 20 of 20
  1. #1
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Smile more fun... with recursion

    I am playing a bit with recursive methods.
    I have an iterative solution for this and yes i know I can use math.pow
    but thats not the point of the exercise.

    I am trying to raise to the power by recursion, and hope some one can nudge me in the right direction. please don't post the solution.
    this is what I have
    my base case is when you get to n ^1 in which case return N
    but also I have to remember that n ^0 == 1

    eg. 2 ^4 == (2*2)^3 == (2*2*2)^2 == (2*2*2*2) ^1

    but my code doesn't work properly
    Java Code:
    private double raiseToPower(double base, int exp) {
    		if (exp == 0){
    			return 1;
    		}else{
    			if (exp == 1)return base;
    		}
    		return  raiseToPower( base * base , exp-1);
    following this code through using 2 ^4
    first time through it returns (2*2 , 3) which is good
    but next time through
    base is now 4 so it returns (4*4), 2) which is bad
    I want it to return ((2*4) ,2)
    then ((2*8) , 1)

    but how to intialise the value that is first passed to to double base so it remains unchanged throughout the recursion.....
    so as the last line would be

    Java Code:
    return  raiseToPower( [COLOR="Red"]the intial value of [/COLOR]base * [COLOR="red"]the recursive vale of [/COLOR]base , exp-1);
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

  2. #2
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    First off, instead of this:
    Java Code:
    private double raiseToPower(double base, int exp) {
    		if (exp == 0){
    			return 1;
    		} else {
    			if (exp == 1)return base;
    		}
    		return  raiseToPower( base * base , exp-1);
    ...you can do this:
    Java Code:
    private double raiseToPower(double base, int exp) {
    		if (exp == 0) {
    			return 1;
    		} else if (exp == 1) {
    			return base;
    		}
    		return  raiseToPower( base * base , exp-1);
    When you find your answer, you may notice that you don't need the else clause at all.

    You're tantalizingly close to the answer, but right now you're saying x^y = (x*x)^(y-1) when you really mean x^y = x*x^(y-1). Subtle but important difference.

    -Gary-

  3. #3
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Also, beware: what happens when I call:
    Java Code:
            double myAnswer = raiseToPower(81, -2);
    ??

    -Gary-

  4. #4
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Default

    Quote Originally Posted by gcalvin View Post
    Also, beware: what happens when I call:
    Java Code:
            double myAnswer = raiseToPower(81, -2);
    ??

    -Gary-
    negative exponents is the next exercise and that means division,, I got that already

    so its just about the brackets, not about intialising the inital value of double base.
    thinking......
    EDIT:
    and which else statement can i lose....
    thinking some more........
    Last edited by sonny; 03-21-2010 at 03:14 AM. Reason: have thunk a bit
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

  5. #5
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Hint: pronounce this out loud, using the name of your method:

    x^y = x * x^(y-1)

    -Gary-

  6. #6
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Quote Originally Posted by sonny View Post
    negative exponents is the next exercise and that means division,, I got that already

    so its just about the brackets, not about intialising the inital value of double base.
    thinking......
    It is about division, yes, but it's also about whether you'll accept a negative exponent argument, and what will happen if you do. Actually, it's not a horrible thing, but give it a try, see what happens, and see if you understand why.

    -Gary-

  7. #7
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Default

    but it's also about whether you'll accept a negative exponent argument, and what will happen if you do.
    I was just gonna write two methods one for positive and one for negative and pass the variable as a result of some kind of intermediate if else method

    but thats getting ahead of myself.... i'm still thinking brackets
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

  8. #8
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Quote Originally Posted by sonny View Post
    I was just gonna write two methods one for positive and one for negative and pass the variable as a result of some kind of intermediate if else method

    but thats getting ahead of myself.... i'm still thinking brackets
    It will end up being easier than that (but you probably will want a separate method for fractional exponents).

    -Gary-

  9. #9
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Quote Originally Posted by sonny View Post
    .... i'm still thinking brackets
    Not brackets exactly (or even parentheses)... remember, say this out loud, using your method name:

    x ^ y = x * x ^ (y - 1)

    -Gary-

  10. #10
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Lightbulb

    YES! :D i think!

    i have to pass back
    base*(base, exp-1)

    and not (base*Base, exp-1)

    just testing it..
    think its right......
    .... yeah really subtle
    not sure about the which else to lose yet but......
    will do some tests.... and figure that in a mo
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

  11. #11
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Well, since you figured it out, I'll just write up the code:
    Java Code:
    int raiseToPower(int base, int exp) {
       if(exp == 0) return 1;
       return base*raiseToPower(base, exp-1);
    }
    You really don't need the extra else if(exp == 1). Sure, the recursion would finish one cycle sooner, but every time you run the method, you will perform two checks instead of one, so I think it's a good trade-off. And of course, this still doesn't check for negative exponents and will just keep going until a stack overflow exception for > 0 exp values.

  12. #12
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    And covering negative exponents is pretty simple too. I'll post the code in white, in case it's a spoiler for Sonny or anybody else (drag your mouse over it to read it).

    Java Code:
    [COLOR="White"]    public double raiseToPower(double base, int exp) {
            if (exp == 0) return 1;
            if (exp < 0 ) {
                return raiseToPower(base, exp + 1) / base;
            }
            return base * raiseToPower(base, exp - 1);
        }[/COLOR]
    Fractional exponents would, I think, be best handled in another method, with double base, int expNum, and int expDenom parameters.

    -Gary-

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

    Default

    All is fine and well but this recursive relation

    x^n == 1 if n == 0 else x*x^(n-1)

    causes n recursive calls; we can do better than that; have a look:

    Java Code:
    int pow(int x, int n) { // n must be >= 0
       if (n == 0) return 1;
       int p= pow(x, n>>>1); p*= p;
       if ((n&1) == 1) return x*p;
       return p;
    }
    This implementation needs 2log(n) recursive calls. e.g. 2^64 doesn't take 64 recursive calls but only 6. This mechanism is called 'divide and conquer' and is quite a powerful trick.

    kind regards,

    Jos
    Last edited by JosAH; 03-21-2010 at 08:37 AM.

  14. #14
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    So to complete JosAH's example for negative exponents, and have it return doubles:

    Java Code:
    	public double pow(double x, int n) {
    		   if (n == 0) return 1;
    		   if (n < 0) return 1 / pow(x, -n);
    		   double p = pow(x, n>>>1);
    		   p *= p;
    		   if ((n&1) == 1) return x*p;
    		   return p;
    	}
    -Gary-

  15. #15
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    To explain the "divide & conquer" trick a little better...

    int n>>>1 gives the same result as int n / 2, but does it in one machine instruction. By shifting all the bits one place to the right, you're dividing by 2 and throwing away the remainder. The line:
    Java Code:
    		   if ((n&1) == 1) return x*p;
    ...takes care of the cases where the exponent is odd, so the remainder was thrown away, by multiplying the base back in to the result.

    So what we're saying is:

    x ^ n = (x ^ (n/2)) * (x ^ (n/2)) where n is even, or
    (x ^ (n/2)) * (x ^ (n/2)) * x where n is odd.
    (again, assuming integer division for n/2)

    So each time through our method we're cutting the remaining number of recursions in half. It's the exact same efficiency benefit you get from a binary tree search compared to a linear search.

    (Now I hope somebody will correct me if I've lied about any portion of this. :D)

    -Gary-

  16. #16
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Default #$##&**%$#@!#$&^%$^!!!! what!!!

    yeah okay figured the (base==1) could go,, that was what i started with for my base condion, which is why it threw me a bit.

    :eek:
    Java Code:
    int pow(int x, int n) { // n must be >= 0
       if (n == 0) return 1;
       int p= pow(x, n>>>1); p*= p;
       if ((n&1) == 1) return x*p;
       return p;
    }
    AAARRRGGGHHH Jos what have you done to my brain!!!!!! You and Gary between you are like some kind of Java guerrilla ontologists!


    have not seen (n>>>1) before ??
    so this is like dividing in binary ?
    or i could say 101010 divided by two or(10 base 2) is 10101
    or 10011 divided by two is 1001 a cool trick just shifting all the digits to the right.
    but its integer division because you cannot have a remainder.

    so im going through with some numbers first Jos's 2 ^64
    2 ^64 is read in
    1st recursion 2 ^32
    2nd recursion 2 ^16
    3rd recursion 2 ^8
    4th recursion 2 ^4
    5th recursion 2 ^2
    6th recursion 2 ^1

    A ha lights flashing -- bells going off ((maybe !!!)
    then p*=p working backwards through the 6 results cos p has been defined 6 times and we havent forgotten about them they are still there . its like theres 6 copies of the method open which have to be resolved...... i think

    so i'm not sure how it does this exactly but sort of says
    return 2^1 squared to its caller ==4

    no no no....... wait.....

    n is now odd...
    so we come to this
    if ((n&1) == 1) return x*p;

    oh right, but first we square p because of p*=p

    so we now have (2 ^1) * (2^1) ---- which i know == 2^2 == 4
    but, i havent forgotten that n ==1 at this point
    so now we come to
    if ((n&1) == 1) return x*p;
    I have no idea what this means, I'm guessing this more binary magic, like maybe some form of binary modular division....
    but from garys explanation i will assume that it is boolean true because n is now odd.

    so okay, return x*p means return 2 * ((2 ^1) * (2^1)) this is == to 8 but its still an expression so its not 8 that is being returned its an expression still

    but its all gone Hazy now and ive got lost as to where this is returned to......
    and my brain is in pieces

    can you walk me through what comes next please










    .etc
    ...
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

  17. #17
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Quote Originally Posted by sonny View Post
    so now we come to
    if ((n&1) == 1) return x*p;
    I have no idea what this means, I'm guessing this more binary magic, like maybe some form of binary modular division....
    This is a bitwise AND operator, the table for it looks like this:
    Java Code:
    x  y  x&y
    0  0   0
    0  1   0
    1  0   0
    1  1   1
    It will return 1, only if given two operands with a value of 1, and since all odd numbers have 1 as their LSB, oddNum&1 returns 1, evenNum&1 returns 0.

  18. #18
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Thumbs up

    Quote Originally Posted by sonny View Post
    so okay, return x*p means return 2 * ((2 ^1) * (2^1)) this is == to 8 but its still an expression so its not 8 that is being returned its an expression still

    but its all gone Hazy now and ive got lost as to where this is returned to......
    and my brain is in pieces can you walk me through what comes next please
    so lets see if i can get through it then.......

    @moonchile

    hey thanks for that
    LSB - Least significant bit - Wikipedia, the free encyclopedia

    so we have
    1) int p= pow(x, n>>>1) doing the work of making the recursive calls
    2) p*=p will then sqaure all the recursions
    3) if ((n&1) == 1) saying if the last bit == 1 (but a more efficient way of doing it than saying if n/2 == 1, because your boolean checking just four possible outcomes using binary ) am shaky here what do x y correspond to x & n or both ns inthe expression 2 * ((2 ^1) * (2^1))

    if n is odd multiply the base back in (x* (p*=p)
    you correct for the one n you chopped off every time p was declared where n was odd
    and then return all the p's back to their callers so it can arrive back at the beginning when all the calls have been answered..

    I can sort of see a problem being spit up into smaller chunks, I am not sure i understand yet the mechanics of it precisely.
    that is a kinda powerful alogrithm, recognizing how and where to do it will take me some practice, i suppose.
    and this is certainly more efficient that Iteration.


    3 ^9
    (3 ^4)
    (3 ^2)
    (3 ^1)
    (3 ^0) return 1 to the int p in the previous call,, where n is odd(1)
    i understand this okay. we see how many calls it takes to get to one then
    we can answer each call and go back again,

    P==(1) p*=p ==1 n (1) is odd 3*1 is returned
    P == (3) p*=p == 9 n is(2) even
    p== (9) P*=P == 81 n si even(4)
    p==(81) p*=p 6561 n is odd (9) return 3*6561


    == 19683 :D
    Last edited by sonny; 03-23-2010 at 12:06 AM.
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

  19. #19
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    OK, let's take the bit manipulation out of it for the moment, as it's only there for efficiency anyway. And we'll put back the method name and parameter names you were originally using, and remove dealing with negative powers for now, in order to keep things simpler.

    So here's what we had before:
    Java Code:
    double raiseToPower(double base, int exp) {
       if (exp == 0) return 1;
       return base * raiseToPower(base, exp - 1);
    }
    But we notice that if exp is large, we're going to be doing a lot of recursing, and we wonder if there's a way to reduce that. We also notice that if exp is even, then base^exp = base^(exp/2) * base^(exp/2). How does that help? Well, it helps because exp/2 means half as much recursion as exp, right?

    So we could just change our method to this:
    Java Code:
        double raiseToPower(double base, int exp) {
            if (exp == 0) return 1;
            if (exp % 2 == 0) { // exponent is even
                double saveThisResult = raiseToPower(base, exp / 2);
                return saveThisResult * saveThisResult;
            }
            return base * raiseToPower(base, exp - 1);
        }
    Make sense so far? All we've done is taken our original method, and added a clause to save us some recursion if our exponent is even. If our exponent is not even, we keep doing things the old way. And guess what -- we've already gained most of the efficiency we're going to get. Because if exp is not even, then it will be next time around (when it's exp - 1)! Isn't that cool?

    Well then, since we noticed that, we could just save the recursion call in the odd case, and write it this way:
    Java Code:
        double raiseToPower(double base, int exp) {
            if (exp == 0) return 1;
            if (exp % 2 == 0) { // exponent is even
                double saveThisResult = raiseToPower(base, exp / 2);
                return saveThisResult * saveThisResult;
            }
            double saveThisResult = raiseToPower(base, exp / 2);
            return base * saveThisResult * saveThisResult;
        }
    Ugh, that's kind of ugly. This is better:
    Java Code:
        double raiseToPower(double base, int exp) {
            if (exp == 0) return 1;
            double saveThisResult = raiseToPower(base, exp / 2);
            if (exp % 2 == 0) { // exponent is even
                return saveThisResult * saveThisResult;
            }
            return base * saveThisResult * saveThisResult;
        }
    and this is better still (because the special case is really when exp is odd, not when it's even):
    Java Code:
        double raiseToPower(double base, int exp) {
            if (exp == 0) return 1;
            double saveThisResult = raiseToPower(base, exp / 2);
            saveThisResult *= saveThisResult;
            if (exp % 2 == 1) { // exponent is odd
                return base * saveThisResult;
            }
            return saveThisResult;
        }
    Now we pretty much have JosAH's version. The final trick is noticing that our math is dealing with 2s, and hey! we're on a binary computer, which means math with 2s is even easier than other math. Among other interesting bits of trivia, int x / 2 == x>>>1 and x % 2 == x & 1. And these bit operators are very very efficient -- single machine instructions. So we just plug them in:
    Java Code:
        double raiseToPower(double base, int exp) {
            if (exp == 0) return 1;
            double saveThisResult = raiseToPower(base, exp >>> 1);
            saveThisResult *= saveThisResult;
            if ((exp & 1) == 1) { // exponent is odd
                return base * saveThisResult;
            }
            return saveThisResult;
        }
    And finally, if exp is negative, just get the answer for its positive counterpart, and return its reciprocal.
    Java Code:
        double raiseToPower(double base, int exp) {
            if (exp == 0) return 1;
            if (exp < 0) return 1 / raiseToPower(base, -exp);
            double saveThisResult = raiseToPower(base, exp >>> 1);
            saveThisResult *= saveThisResult;
            if ((exp & 1) == 1) { // exponent is odd
                return base * saveThisResult;
            }
            return saveThisResult;
        }
    Now for the real moral of the story -- the version we had without the divide-and-conquer and bit manipulation was probably good enough for whatever we were likely to be doing with it. Premature optimization can be dangerous, and is very often wasteful. If you have code that works, and that you understand, you should generally leave it alone. If you do go messing with it, and finding clever tricks, make sure you test it and confirm that it behaves the same way your original method did (except faster, we hope). And comment the clever parts copiously.

    -Gary-

  20. #20
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Thumbs up Brilliant!

    cheers Gary
    thats a brilliant summary of what this thread is about and how the code developed.
    I should imagine that its a thread i will come back to read a few times.


    kind regards

    Sonny
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

Similar Threads

  1. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  2. Recursion
    By kathyla18 in forum New To Java
    Replies: 2
    Last Post: 04-09-2009, 02:26 AM
  3. Recursion
    By jachandru in forum New To Java
    Replies: 1
    Last Post: 01-24-2009, 12:52 PM
  4. Recursion help
    By rjg_2186 in forum New To Java
    Replies: 1
    Last Post: 01-02-2009, 08:03 AM
  5. recursion
    By kdeighan in forum New To Java
    Replies: 3
    Last Post: 01-25-2008, 09:48 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
  •