Convert number in a certain base to a decimal number using recursion

Question

My assignment is to create a recursive method makeDecimal that when passed a number (that is represented by a String) and its base, converts the number to base 10. You will need to use the method Integer.parseInt(str). (Hint: use substrings.) This method takes a String and returns the integer form of it.

For example, Integer.parseInt("21"); will return the int 21.

Here are some examples of how makeDecimal works:

makeDecimal("11", 2) will return 3.

makeDecimal("100", 4) will return 16.

Here was my attempt at it:

public static double makeDecimal(String number, int base){
    int len = number.length();
    double f = 0;

    if(len <= 0)
        return 0;
    else{
        makeDecimal(number,base);

        double temp = Integer.parseInt(number.substring(len - 1, len + 1));
        f = f + temp * Math.pow(3, len-1);
    }

    len--;
    return f;
}

However, I get an "overflow error", and I don't know if it even is written correctly.

Answer 1

You are recursing with exactly the same arguments that were passed in. As a result, the call will itself recurse the same way, until the stack overflows. That's not how recursion is supposed to work. Instead, you need to figure out how to do one piece of the problem in the current call and then recurse to do a smaller problem.

In your code, it's not even clear what logic you are using. (What's the point of computing 3^len-1?) Try this instead:

• If the input string has length 0, the answer is 0 (that part you got right)
• Otherwise, take the last digit and parse it in the current base. Then the answer is that value plus base times the value of everything up to but not including the last digit of the input. (Hint: this is a good place to use recursion.)

You should be able to translate that description into the appropriate method calls and use of substring().

Oh, one other thing: there's no reason to be using double values here. Just stick with int variables throughout. You won't be needing Math.pow().

Answer 2

Here is simplest solution using recursion, substring and Integer.parseInt:

public int makeDecimal(String value, int base) {
    // exit from recursion
    if (value.length() < 1) 
        return 0;

    //parsing last character of string
    int charValue = Integer.parseInt(value.substring(value.length() - 1), base);

    //calling recursion for string without last character
    return makeDecimal(value.substring(0, value.length() - 1), base) * base + charValue;
}