indexOf的递归实现

Question

我已经在这里和其他地方阅读了许多以前的问题，但我还没有找到我需要的东西。我需要编写 indexOf 的递归实现。问题是我不能使用任何局部变量，只能提供一个字符串和一个字符作为输入。

该方法应该 return 一个介于 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);
    }                                  
}

我特别看到了this，但是可以不用变量写吗？谢谢

Answer 1

您链接的答案似乎是一个不错的答案...我建议只需将其中使用的变量实例替换为调用变量存储的方法即可。

下面我简单编辑一下代码：

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

Answer 2

如果您不需要局部变量，则需要在内部方法中进行递归。

优点是速度快得多，因为它不必创建新的 String 对象，并且逻辑是尾递归的，如果与优化它的语言一起使用的话。

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

indexOf的递归实现

Recursive implementation of indexOf

java

indexof