more fun... with recursion

[sonny]

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

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

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

[gcalvin]

First off, instead of this:

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:

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-

[gcalvin]

Also, beware: what happens when I call:

        double myAnswer = raiseToPower(81, -2);

??

-Gary-

[sonny]

Also, beware: what happens when I call:

        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........

[gcalvin]

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

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

-Gary-

[gcalvin]

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-

[sonny]

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

[gcalvin]

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-

[gcalvin]

.... 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-

[sonny]

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

[m00nchile]

Well, since you figured it out, I'll just write up the 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.

[gcalvin]

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).

[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-

[JosAH]

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:

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

[gcalvin]

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

	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-

[gcalvin]

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:

		   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-

[sonny]

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:

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
...

[m00nchile]

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:

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.

[sonny]

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

[gcalvin]

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:

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:

    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:

    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:

    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):

    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:

    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.

    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-

[sonny]

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