Results 1 to 20 of 20
Thread: more fun... with recursion
 03212010, 03:07 AM #1
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 , exp1);
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 , exp1);
: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
 03212010, 03:32 AM #2Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
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 , exp1);
Java Code:private double raiseToPower(double base, int exp) { if (exp == 0) { return 1; } else if (exp == 1) { return base; } return raiseToPower( base * base , exp1);
You're tantalizingly close to the answer, but right now you're saying x^y = (x*x)^(y1) when you really mean x^y = x*x^(y1). Subtle but important difference.
Gary
 03212010, 03:44 AM #3Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
Also, beware: what happens when I call:
Java Code:double myAnswer = raiseToPower(81, 2);
Gary
 03212010, 04:08 AM #4
Last edited by sonny; 03212010 at 04: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
 03212010, 04:10 AM #5Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
Hint: pronounce this out loud, using the name of your method:
x^y = x * x^(y1)
Gary
 03212010, 04:14 AM #6Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
 03212010, 04:24 AM #7but it's also about whether you'll accept a negative exponent argument, and what will happen if you do.
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
 03212010, 04:26 AM #8Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
 03212010, 04:29 AM #9Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
 03212010, 04:35 AM #10
YES! :D i think!
i have to pass back
base*(base, exp1)
and not (base*Base, exp1)
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
 03212010, 07:29 AM #11Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 6
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, exp1); }
 03212010, 07:50 AM #12Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
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]
Gary
 03212010, 09:35 AM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,943
 Blog Entries
 7
 Rep Power
 22
All is fine and well but this recursive relation
x^n == 1 if n == 0 else x*x^(n1)
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; }
kind regards,
JosLast edited by JosAH; 03212010 at 09:37 AM.
 03212010, 02:43 PM #14Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
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; }
 03212010, 03:15 PM #15Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
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;
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
 03222010, 02:59 AM #16
#$##&**%$#@!#$&^%$^!!!! 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; }
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
 03222010, 07:41 AM #17Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 6
 03232010, 12:52 AM #18
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 :DLast edited by sonny; 03232010 at 01: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
 03232010, 02:19 AM #19Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
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); }
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); }
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; }
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; }
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; }
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; }
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; }
Gary
 03232010, 06:09 AM #20
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

recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
Recursion
By kathyla18 in forum New To JavaReplies: 2Last Post: 04092009, 02:26 AM 
Recursion
By jachandru in forum New To JavaReplies: 1Last Post: 01242009, 01:52 PM 
Recursion help
By rjg_2186 in forum New To JavaReplies: 1Last Post: 01022009, 09:03 AM 
recursion
By kdeighan in forum New To JavaReplies: 3Last Post: 01252008, 10:48 PM
Bookmarks