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对象，而且如果与优化它的语言一起使用，逻辑是尾部递归的。

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