Recursive manual way to convert int to string (without anything like an array, a list, or parsing stuff) for positive and negative numbers

Question

hello i worked on a recursive method to convert from int to string fully manual way, and i wanna know if that recursive method is efficient or not, and if you could help me to improve the code. Im new to algorithms so don't blame me if something looks like ugly... I've search on the internet but never looked for something like that :

public class IntToString {

public static String intToString(int number) {
    return intToString(number, "", false);
}

private static String intToString(int number, String answer,
        boolean isNegative) {

    if (number < 0 && isNegative == false) {
        isNegative = true;
        number = -number;
    }

    if (number == 0)
        if (isNegative)
            return "-" + answer;
        else
            return answer;

    System.out.println(number);
    return intToString(number / 10, answer = number % 10 + answer,
            isNegative);
}

// test
public static void main(String[] args) {

    String ans = intToString(-324234);
    System.out.println(ans);

}

}

Answer 1

No, it's not very efficient. Though it could be worse. At least it's still O(N) where N is the number of decimal digits in the given number.

• invertInt is not really needed. You are using it because you are appending it to the answer that you pass down the the recursions, which will cause that number to be inverted. But there are at least two other ways to do it so that it won't be inverted.
• If you note, there is only a very slight difference between the the way you handle negative numbers and positive numbers. Perhaps you can just run the same procedure for both of them, if you remember that processing a negative number is the same as processing its positive opposite, and tacking the - when you're done.
• There is no reason for all the flags for negative and inversion. Both of them are only done at the top level. So you can do those things at the intToString(int number) function and not in your recursive function, and save yourself a lot of condition checking, and of course, the replaceAll() call.
• There is no need to pass down the answer. You can base your return value on what the recursive call returned. Remember that for numbers like 1,2,3, you'll get the string '1','2','3'. So if you have 23, and you pass down 2, you can use the 2 you got to build your answer.
• Your algorithm does not return the correct answer for 0. It's the correct answer when you think in recursive terms, but not when you call it with 0 from main. There are at least two ways to handle that.

And a bit of style advice:

• Always indent your code properly.
• You don't need to compare boolean values to true or false. If you have a boolean variable x, you can use if (x) or if (!x) rather than if (x==true) and if (x==false). Name your boolean variables in a way that will make this more intuitive, like isNegative or needsInversion. An if (isNegative) makes sense when you read it.

---

More detailed information in case you could not find the solution:

How do we avoid the inversion? There are two ways, basically. If you insist on passing down the answer, then instead of:

answer += num % 10;

Use:

answer = ( num % 10 ) + answer;

That is - append it to the left of the answer, not its right.

The approach I prefer is using the answer from the lower level. Suppose you have the number 123. So you pass down 12, and you get back the answer "12". Then you can use

return answer + ( num % 10 );

which will give you "123". This time, it's appended to the right.

---

Finally, here is the complete solution:

public static String intToString( int n ) {
    if ( n == 0 ) {
        return "0";
    } else if ( n < 0 ) {
        return "-" + positiveIntToString( -n );
    } else {
        return positiveIntToString(n);
    }
}

private static String positiveIntToString( int n ) {
    if ( n == 0 ) {
        return "";
    } else {
        return positiveIntToString( n / 10 ) + ( n % 10 );
    }
}

You have the public function that is what you expose to the world. The recursive function is private, and it is only called for positive numbers. If called with zero, it will return an empty string, which is good for the recursion, but not as a real solution.

So the public function first checks two possible issues. If the number is zero, it shouldn't be passed to the private function because it will not return the correct answer. Instead, just return the string "0", as it is the correct answer.

For a negative number, all we need to do is do the work for its counterpart, -n, which is positive and so will be acceptable to the private function. And then we add the "-" in front.

The recursive function for positive integers then becomes very simple: if it's zero, return empty string. For anything else, call itself with n/10, tack the n%10 to the right side of the result, and return that.

Here is also an alternative solution, without a private method:

public static String intToString( int n ) {
    if ( n == 0 ) {
        return "0";
    } else if ( n < 0 ) {
        return "-" + intToString( -n );
    } else if ( n < 10 ) {
        return "" + (n%10);
    } else {
        return intToString(n/10) + (n%10);
    }
}

I actually consider this to be a slightly less efficient solution, because we do two more checks on each level. The check for negative will only be true once, at the top level. The check for zero will only be true if the function is called with zero in the first place. The check for single digit numbers is the current recursion end (because we can't stop the recursion at zero, otherwise we'll always get an extra "0" at the beginning).