Рекурсивная реализация indexOf

Question

Я уже читал много предыдущих вопросов здесь и в других местах, но я не нашел то, что мне нужно. Мне нужно написать рекурсивную реализацию indexOf. Проблема в том, что я не могу использовать какие-либо локальные переменные и должен давать в качестве входных данных только строку и символ.

Метод должен возвращать значение от 0 до длины строки - 1, если символ был найден или -1, если его там нет. Я знаю, что фактический indexOf также позволяет вам искать строку, но этот метод упрощен.

Я пробовал это, но это довольно глупо, поскольку я использовал реальное indexOf :

public static int indexOf(String s, char c){

    if(s.indexOf(c) < 0){       // I'd like to change this
        return -1;
    }

    if (s.length() == 0)        //base case #1
    {                           
        return -1;              
    } 
    else if (s.charAt(0) == c)  //base case #2
    {                           
        return 0;               
    }
    else {
        return 1 + indexOf(s.substring(1), c);
    }                                  
}

Я видел это в частности, но так ли это возможность написать это без переменных? Спасибо

Answer 1

Если вам не нужны локальные переменные, вам нужно выполнить рекурсию во внутреннем методе.

Преимущество состоит в том, что это намного быстрее, так как ему не нужно создавать новые String объекты и logi c является хвост-рекурсивным, если используется с языком, который оптимизирует это.

public static int indexOf(String s, char c) {
    return indexOf0(s, c, 0);
}
private static int indexOf0(String s, char c, int index) {
    if (index == s.length())
        return -1;
    if (s.charAt(index) == c)
        return index;
    return indexOf0(s, c, index + 1);
}

Answer 2

Ответ, который вы связали, кажется хорошим ... Я рекомендую просто заменить экземпляры используемой в нем переменной на вызов метода, который хранит переменная.

Ниже я просто отредактирую код:

public static int indexOf(char ch, String str) {
    // Returns the index of the of the character ch

    if (str == null || str.equals("")) {
        // base case: no more string to search; return -1
        return -1;
    } else if (ch == str.charAt(0)) {
        // base case: ch is at the beginning of str; return 0
        return 0; 
    }

    return indexOf(ch, str.substring(1)) == -1 ? -1 : 1 + indexOf(ch, str.substring(1));
}