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

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

Code:

`return raiseToPower( [COLOR="Red"]the intial value of [/COLOR]base * [COLOR="red"]the recursive vale of [/COLOR]base , exp-1);`

#$##&**%$#@!#$&^%$^!!!! 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:

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

...