Recursive method construction
Here is my probl开发者_开发百科em:
Write a recursive method called
binaryToDecimal
. The method should convert a binary string of bits to a base 10 integer. A sample call for an object from ourRecursionExamples
class would beanswer = example.binaryToDecimal("101111")
The integer returned would be 47.
I need help to get going with this problem. I know it would be an if-else loop, but how to go about it boggles me. (This is the eclipse environment).
If you want to solve it recursivly, consider that the for a binary string, you can convert it to an integer by adding 1 or 0 based on the rightmost number, adding 2 times this function based on the rest of the string.
It would look something like this in pseudocode
// input is an integer of 1's and 0's
def f( int binaryString ):
int lastDigit = binaryString % 10 // Get the last digit
int restOfString = binaryString / 10 // Remove the last digit
return lastDigit + (2 * f(restOfString)) // add the last digit to twice f
// applied to the rest of the string
You'll also have to check for when the rest of the string is reduced to nothing as an end condition, but this is the basic logic for the method.
What you want to do is simple:
- Think of exit conditions - what is the most atomic string it can process. Bonus points if your methods returns an appropriate error on empty string.
- Think of how to use your recursive functions. Reese already posted a good solution if you ignore code used to extract lastDigit and restOfString.
Here is a more Java-like pseudo code, without revealing too much:
public int binToDec(String binary)
{
if (end_conditions) return int
int lastDigit = Integer.process
String restOfString = binary.substring
return lastDigit + 2* binToDec(restOfString);
}
int binaryToDecimal(String s){
if (s.isEmpty() || Integer.parseInt(s)==0){ // It's a little weird because the only
return 0; // argument is a String.
}
else{
int number = Integer.parseInt(s);
int lastDigit = number % 10;
int remainder = number \ 10;
return lastDigit + 2 * binaryToDecimal(String.valueOf(remainder))
}
}
精彩评论