Сколько итераций выполняется до StackOverflowError

Question

В настоящее время я пишу программу для проверки чек на Android, которая получает пользовательские входы (арабские цифры) и превращает их в номера чеков. Например, четыре тысячи пять долларов и без центов, что-то в этом роде. Английская часть немного легка, и я закончил ее. Теперь я пишу китайскую версию в другой деятельности. На этот раз я использовал рекурсивный алгоритм, потому что китайские цифры написаны очень по-разному. Это алгоритм: (Комментарии переводы)

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))); 
} 

Как вы можете видеть, у меня есть рекурсивный метод. Он преобразует первую цифру и вызывает себя, чтобы преобразовать остальные. Поэтому, если есть очень большое количество, это будет называть себя много раз. Поэтому я хочу спросить, сколько раз метод может вызвать себя до появления StackOverflowError?

Answer 1

Рекурсия хорошо работает для алгоритмов O (log N), таких как быстрая сортировка и поиск по линейному делению пополам.

Он работает намного менее хорошо для O (N), который является вашим случаем.

Как правило, избегайте рекурсивных алгоритмов в таких случаях. Они могут всегда быть преобразованы в цикл.

Ваш конкретный ответ: он будет варьироваться от JVM до JVM. Все, что было около 20, было бы сомнительным.