How many iterations is executed before StackOverflowError

Question

I am currently writing an Android cheque writer program that gets user inputs (arabic numbers) and turn them into cheque-style numbers. For example, Four Thousand Five Dollars and No Cents Only, something like that. The English part is kind of easy and I finished it. Now I am writing a Chinese version in a different activity. This time I used a recursive algorithm because the Chinese numbers are written very differently. This is the algorithm: (The comments are translations)

private String convertNumberString(String number) {
    if (number.equals ("")) {
        return "請輸入幣值"; //Please enter amount
    }

    String[] twoParts = number.split ("\\.");
    String integerPart = twoParts[0];
    String decimalPart;
    try {
        decimalPart = twoParts[1];
    } catch (ArrayIndexOutOfBoundsException ex) {
        decimalPart = "";
    }

    if (new BigInteger (integerPart).compareTo (new BigInteger ("9999999999999999")) > 0) {
        return "輸入的幣值過大，必須小於或等於 9999999999999999"; //The amount is too large, must be less than or equal to 9999999999999999
    }

    if (new BigInteger (integerPart).compareTo (new BigInteger ("1")) < 0) {
        return "輸入的幣值過小，必須大於或等於 1"; //The amount is too small, must be greater than or equal to 1
    }

    String integerString;
    String decimalString = "";

    integerString = convertInteger (integerPart);

    if (decimalPart.equals ("") || Integer.parseInt (decimalPart) == 0) {
        decimalString = "";
    } else {
        if (decimalPart.length () < 2) {
            decimalPart += "0";
        }
        String jiao = decimalPart.substring (0, 1); //jiao = 角
        String fen = decimalPart.substring (1, 2); // fen = 分
        if (!jiao.equals ("0")) {
            decimalString += convertNumber (getDigitFromString (jiao, 0)) + "角"; // 角 = 10 cents 分 = 1 cent
        }

        if (!fen.equals ("0")) {
            decimalString += convertNumber (getDigitFromString (fen, 0)) + "分";
        }
    }

    return integerString + "圓" + decimalString + "正"; //圓 = dollars 正 = only
}

private String convertNumber (int i) {
    switch (i) {
        case 0:
            return "零"; //zero
        case 1:
            return "壹"; //one
        case 2:
            return "貳"; //you get the idea...
        case 3:
            return "叁";
        case 4:
            return "肆";
        case 5:
            return "伍";
        case 6:
            return "陸";
        case 7:
            return "柒";
        case 8:
            return "捌";
        case 9:
            return "玖";
        default:
            return "";
    }
}

private String getThatWord (int index) {
    switch (index) {
        case 0:
            return "";
        case 1:
            return "拾"; //ten
        case 2:
            return "佰"; //hundred
        case 3:
            return "仟"; //thousand
        case 4:
            return "萬"; //ten thousand
        case 5:
            return "億"; //hundred million
        case 6:
            return "兆";//trillion
        default:
            return ""; //I know, Chinese numbers are different.
    }
}

//here is the recursive part
private String convertInteger (String number) {
    if (number.length () < 5) {
        if (number.length () == 1)
            return convertNumber (getDigitFromString (number, 0));
        String finalString = convertNumber (getDigitFromString (number, 0)) +
                getThatWord (number.length () - 1);
        number = number.substring (1);

        if (Integer.parseInt (number) == 0) {
            return finalString;
        }

        for (int i = 0 ; i < number.length () ; i++) {
            if (number.charAt (i) == '0')
                continue;
            return finalString + convertInteger (number.substring (i));
        }
        return null;
    } else {
        int charsToRead = number.length () % 4;
        if (charsToRead == 0) charsToRead = 4;
        String firstPart = number.substring (0, charsToRead);
        String secondPart = number.substring (charsToRead);
        int thatWordIndex = 3 + number.length () / 4;

        if (charsToRead == 4) {
            thatWordIndex--;
        }
        String thatWord = getThatWord (thatWordIndex);

        return convertInteger (firstPart) + thatWord + convertInteger (secondPart);
    }
}

private int getDigitFromString (String str, int index) {
    return Integer.parseInt (Character.toString (str.charAt (index)));
}

As you can see, I have a recursive method. It converts the first digit and call itself to convert the rest. So if there is a extremely large number, it would call itself a lot of times. So I want to ask, how many times can a method call itself before a StackOverflowError occurs?

Answer 1

Recursion works well for algorithms of O(log N), such as quick sorting and linear bisection searches.

It works much less well for O(N), which is your case.

As a rule of thumb, avoid recursive algorithms in such cases. They can always be transformed to a loop.

Your specific answer: it will vary from JVM to JVM. Anything over about 20 would be questionable.