programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Paul Clapham
• Bear Bibeault
• Jeanne Boyarsky
Sheriffs:
• Ron McLeod
• Tim Cooke
• Devaka Cooray
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Jj Roberts
• Stephan van Hulst
• Carey Brown
Bartenders:
• salvin francis
• Scott Selikoff
• fred rosenberger

# Recursion with exponents

Ranch Hand
Posts: 31
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 ]

Ranch Hand
Posts: 490
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.

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 ]

doburomirushii nikku
Ranch Hand
Posts: 31
Yeah I mean log(base 8) 2. Thanks for the reply...I will look that up and see if it helps.

Edit: Figured it out...

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

Rusty Shackleford
Ranch Hand
Posts: 490
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.

 You will always be treated with dignity. Now, strip naked, get on the probulator and hold this tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton