# Recursion with exponents

doburomirushii nikku

Ranch Hand

Posts: 31

posted 10 years ago

I'm trying to do a recursion that will find log 2^8 and return 3. Also if it gets log 2^15 it should return 3 also (so it rounds it down). Then I want to design a similar recusion method that will only find a perfect log such as log 2^8 = 3, but return -1 for log 2^15.

Here is my code for it.

I know you need a base case for recusion so that would be if the value was 1...then whatever the base is would have to be rasied to the 0 power. Then there is also if base == value...The method would return 1.

But I'm now really sure how my recursion case should go. I understand that what I'm doing is going to do 2, then 2 * 2, then 4 * 4, ect., which is incorrect. So how can I preserve the base value?

I think I want the method to do this:

1 + floorLog(2, 8)

1 + floorLog(2 * 2, 8)

1 + floorlog(2 * 2 * 2, 8)

At this point I want it to return in my base case...I'm just not sure how to translate it recursively.

Thanks.

Edit: I forgot...I need to do it without importing java.math

[ April 10, 2006: Message edited by: doburomirushii nikku ]

Here is my code for it.

I know you need a base case for recusion so that would be if the value was 1...then whatever the base is would have to be rasied to the 0 power. Then there is also if base == value...The method would return 1.

But I'm now really sure how my recursion case should go. I understand that what I'm doing is going to do 2, then 2 * 2, then 4 * 4, ect., which is incorrect. So how can I preserve the base value?

I think I want the method to do this:

1 + floorLog(2, 8)

1 + floorLog(2 * 2, 8)

1 + floorlog(2 * 2 * 2, 8)

At this point I want it to return in my base case...I'm just not sure how to translate it recursively.

Thanks.

Edit: I forgot...I need to do it without importing java.math

[ April 10, 2006: Message edited by: doburomirushii nikku ]

Rusty Shackleford

Ranch Hand

Posts: 490

posted 10 years ago

You when say log 2^8 do you mean log 256, 2^8= 256

Or log(base 8) 2?

log 2^8 ~=2.408 rounded down is 2.

log(base2) 8 is 3.

I am just curious about your notation.

Just a few thoughts off the top of my head. I gotta get to class, sorry for the lack of details.

That looks like infinite recursion to me, value stays the same, while base base increases and there is no guarantee that it will ever equal value. You need a value that changes each recursive call that is used for the exit condition.

Google for the power series of log and use the fact that log(base n) x <==> log(base 10) x/log(base n). Hopefully that can point you in the right direction.

[ April 10, 2006: Message edited by: Rusty Shackleford ]

Or log(base 8) 2?

log 2^8 ~=2.408 rounded down is 2.

log(base2) 8 is 3.

I am just curious about your notation.

public static int floorLog(int base, int value){

if (value == 1)

{

return 0;

}

if (base == value)

{

return 1;

}

else

{

return 1 + floorLog(base * base, value);

}

}

Just a few thoughts off the top of my head. I gotta get to class, sorry for the lack of details.

That looks like infinite recursion to me, value stays the same, while base base increases and there is no guarantee that it will ever equal value. You need a value that changes each recursive call that is used for the exit condition.

Google for the power series of log and use the fact that log(base n) x <==> log(base 10) x/log(base n). Hopefully that can point you in the right direction.

[ April 10, 2006: Message edited by: Rusty Shackleford ]

"Computer science is no more about computers than astronomy is about telescopes" - Edsger Dijkstra

doburomirushii nikku

Ranch Hand

Posts: 31

Rusty Shackleford

Ranch Hand

Posts: 490

posted 10 years ago

Good job.

I should have mentioned that when using power series it gives a way to figure it out to as many decimal places as you need, and is a bit of a heavyweight solution for your specific problem. Sorry about that. However, if the next assignment adds to it, by letting the accuracy be determined at runtime, you have the tools to do that.

I should have mentioned that when using power series it gives a way to figure it out to as many decimal places as you need, and is a bit of a heavyweight solution for your specific problem. Sorry about that. However, if the next assignment adds to it, by letting the accuracy be determined at runtime, you have the tools to do that.

"Computer science is no more about computers than astronomy is about telescopes" - Edsger Dijkstra