Converting String of binary digits to decimal number... using recursion

Question

Comp sci professor gave us this problem in our homework... I'm not sure how to proceed and the code I have written seems to be failing miserably. Here is the prompt:

(binary to decimal) Write a recursive method that parses a binary number as a string into a decimal integer. The method header is:

public static String bin2Dec(String binaryString)

write a test program that prompts the user to enter a binary string and displays its decimal equivalent.

Any help greatly appreciated. Here is my code as follows:

import java.util.Scanner;

public class HW04_P5 {
    static int index = 0;
    static int power = 0;
    static int number = 0;
    static boolean exit = false;

    @SuppressWarnings("resource")
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        System.out.print("  Enter a binary number to convert to decimal: ");
        String in = scan.nextLine();
        index = in.length()-1;
        System.out.print("  Binary number converted to decimal:          "+bin2Dec(in));
    }

    public static String bin2Dec(String in)
    {
        if((in.substring(index,index+1).equals("1"))&&(index>0))
        {
            number += Math.pow(2,power);
            System.out.print(number);
            power++;
            index--;
            bin2Dec(in);
        }
        else if((in.substring(index,index+1).equals("0"))&&(index>0))
        {
            power++;
            index--;
            bin2Dec(in);
        }
        System.out.print(number);
        return "";
    }
}

Looks like you are almost there, but to simplify I would just look at the last digit of the string and then pass a new new String to bin2Dec that is a substring of the in String. i.e. no need to have index — Scary Wombat
– Scary Wombat, Commented Apr 9, 2015 at 4:57

Edward Doolittle · Accepted Answer · 2015-04-09 05:40:10Z

2

It's cleaner not to have the extra variables index, power, and p. Just process the string from right to left. You also don't want the "global" variable number tracked outside the recursive function ... it's confusing and weird. You want all the state carried inside the recursive functions, in my opinion. Even with those restrictions, you can still do it in essentially two lines:

public static int bin2Dec(String s) {
  if (s == null || s.isEmpty()) return 0;
  else return s.charAt(s.length()-1)-48+2*bin2Dec(s.substring(0,s.length()-1));
}

That may not be the clearest solution, but it is the most elegant, I think. Clarity could be improved by breaking the else clause into several lines. 48 is the Unicode character number for 0, which is maybe not the best way to convert the characters '0' and '1' to their respective numbers.

answered Apr 9, 2015 at 5:40

Edward Doolittle

4,1102 gold badges18 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

squeeler642 Over a year ago

This worked perfectly. Had a little trouble following this code at first but that helps me a lot in the way of understanding how to compress/condense code. Thanks again for the tip.

Rohit Jain · Accepted Answer · 2015-04-09 04:59:50Z

First: You're printing the number in the if condition, that too without \n. The output you get would be printed number in multiple calls.

Secondly, the condition index > 0 should be index >= 0, else you'll miss the test of 0th index. And that condition should be before &&, not after it.

Thirdly, return number from the method, instead of printing it there.

Here's the modified method with above changes:

public static String bin2Dec(String in) {
    if ((index >= 0) && (in.substring(index, index + 1).equals("1"))) {
      number += Math.pow(2, power);
      power++;
      index--;
      bin2Dec(in);
    } else if ((index >= 0) && (in.substring(index, index + 1).equals("0"))) {
      power++;
      index--;
      bin2Dec(in);
    }
    return "" + number;
}

However, I still see lot of duplication there. You can use String#charAt() method, instead of substring(), since you're really checking for single character. Here's the simplified version of your method:

public static String bin2Dec(String in) {
    if (index < 0) {
      return "" + number;
    }
    if (in.charAt(index) == '1') {
      number += Math.pow(2, power);
    }
    power++;
    index--;
    return bin2Dec(in);
}

Elliott Frisch · Accepted Answer · 2015-04-09 05:06:40Z

0

First, define a private version that also takes a position like

private static int bin2Dec(String in, int p) {
    if (in == null || in.isEmpty() || p >= in.length()) {
        return 0;
    }
    int s = (in.charAt(p) == '1' ? 1 : 0) << in.length() - p - 1;
    return s + bin2Dec(in, p + 1);
}

Note that we first define a stop condition, then determine if the character at that position is a 1 and then shift left by the length of the String (minus that position and minus one because Java uses zero based indexing). Then recurse adding that value to the return value. Finally, the public method is just

public static int bin2Dec(String in) {
    return bin2Dec(in, 0);
}

answered Apr 9, 2015 at 5:06

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

Collectives™ on Stack Overflow

Converting String of binary digits to decimal number... using recursion

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related