使用递归在字符串中查找一个字符

Question

我想要找到字符串中第一个字母的位置。例如，苹果中的p应该返回1。这是我的代码：

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

    if (str == null || str.equals("")) {
        return -1;
    } else if(ch == str.charAt(0)) {
        return 1+ indexOf(ch, str.substring(1));
    }

    return indexOf(ch, str.substring(1));
}

它似乎没有返回正确的值。

- user3496026

---

你为什么不使用String.indexOf(int ch)？ - user1907906

@LutzHorn 作业 - 你敢打赌吗？ :) - user2864740

Answer 1

我会给你一些提示：

1. 当你找到信件后，就不需要再进一步递归了。此外，考虑在这种情况下应该返回什么。
2. 当递归时，请考虑函数应该返回什么。
3. 如果递归调用返回 -1，是否有任何特殊操作需要执行？

- NPE

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

    // recursive step
    int subIndex = indexOf(ch, str.substring(1));

    return subIndex == -1 ? -1 : 1 + subIndex;
}

你的尝试存在两个问题：

在 else if 部分中，你已经找到了字符，所以正确的做法是停止递归，但你却继续了它。

在你最后的返回语句中，如果最终找到了字符，你需要将递归调用加1，作为累积索引号的一种方式。

- JLRishe

---

我本来想点赞，但注意到你的逻辑中至少有一个缺陷。如果你试图使用字符串中没有的字母，则只会得到最后一个字母的索引。 - Paul Sasik

@PaulSasik 看起来你和我同时注意到了这一点。现在应该已经修复了。 - JLRishe

很酷。+1和其他一些词。 - Paul Sasik

@JLRishe +1 对于你的递归步骤。我要说真的很聪明。在递归步骤中，我在 C++ 中使用了 "return 1+indexOf(s.substr(1,s.length()),c)" 这个方法，除了 Paul Sasik 指出的情况外，它运行得很好。 - i.AsifNoor

Answer 3

这是另一种变化。而不是调用substring，你可以稍微修改函数以传递下一个要检查的索引。请注意，递归是以索引0启动的。(实际上，您可以从任何索引开始。还有一些错误检查，以防字母未找到。在apple中寻找x将返回-1。)

public static void main(String []args){  
    System.out.println("Index: " + indexOf('e', "apple", 0));
    System.out.println("Index: " + indexOf('x', "apple", 0));
    System.out.println("Index: " + indexOf('p', "Mississippi", 3));
    System.out.println("Index: " + indexOf('p', "Mississippi", 908));
}

public static int indexOf(char ch, String str, int idx) {
    // check for garbage data and incorrect indices
    if (str == null || str.equals("") || idx > str.length()-1) 
        return -1;

    // check to see if we meet our condition
    if (ch == str.charAt(idx)) 
        return idx;

    // we don't match so we recurse to check the next character
    return indexOf(ch, str, idx+1);
}

输出结果：

索引：4
索引：-1
索引：8
索引：-1

- Paul Sasik

---

idx = indexOf(ch, str, ++idx); 这让我感到不舒服。为什么不用 return indexOf(ch, str, idx + 1) 呢？ - JLRishe

@JLRishe：我刚刚发布了一篇关于你的尴尬评论的编辑。 :-) - Paul Sasik

确实是这样。 :) 我仍然认为在这里使用 idx + 1 更好。没有必要增加 idx 变量的值。 - JLRishe

@JLRishe：+1 好观点。idx+1 更易读和直观，特别是对于新手来说。不确定为什么我之前用了前缀的方式。可能是因为脑子里想着 for 循环。 - Paul Sasik

Answer 4

如果我们必须使用递归，那么可以尝试这个：

class RecursiveFirstIndexOf {

public static void main(String[] args) {
    System.out.println(indexOf('p', "apple", 0));
}

static int indexOf(char c, String str, int currentIdx) {

    if (str == null || str.trim().isEmpty()) {
        return -1;
    }

    return str.charAt(0) == c ? currentIdx : indexOf(c, str.substring(1), ++currentIdx);

}}

- Anshu

---

那是一个问题，而不是一个答案。 - kai

我的意思是 Java 已经提供了 indexOf 方法，为什么不直接使用它来代替编写相同功能的方法呢？ - Anshu

我知道，但问题说：“使用递归”，而不是任何内置方法。无论如何，这不是一个问题。也许是一条评论。 - kai

递归查找字符串中字母索引的唯一原因是为了练习递归。这就是关键词：练习。发帖者可能刚开始学习Java，这是作业、实验任务或其他类似的学术事项。 - Paul Sasik

Answer 5

为什么不直接做呢？

public static void main(String[] args) {
    String str = "abcdef";
    for (int idx = 0; idx < str.length(); idx++) {
        System.out.printf("Expected %d, found %d\n", idx, indexOf(str.charAt(idx), str, 0));
    }
    System.out.printf("Expected -1, found %d\n", indexOf(str.charAt(0), null, 0));
}

public static int indexOf(char ch, String str, int index) {
    if (str == null || index >= str.length()) return -1;
    return str.charAt(index) == ch ? index : indexOf(ch, str, ++index);
}

输出：

Expected 0, found 0
Expected 1, found 1
Expected 2, found 2
Expected 3, found 3
Expected 4, found 4
Expected 5, found 5
Expected -1, found -1

- Harmlezz

---

我永远不会理解为什么有些人使用 ++variable，当他们显然认为 variable + 1 太长了。 - JLRishe

Answer 6

首先：递归有两个支柱，即基本情况和一般情况。

基本情况（终止点）是递归终止的地方，而一般情况则是程序不断执行直到找到基本情况。

您可以尝试这个例子，其中count是一个全局静态变量。

public static int indexOf(char ch, String str)
{
  // Returns the index of the of the character ch
  if (str == null || str.Equals(""))     //Base Case
  {
     if (count != 0)
     {
        if(str.Length == 0)
           return -1;  
        return count;
     }
     else
        return -1;          
  }
  else if (ch == str.CharAt(0))          //Base Case  
     return 1 + count; 
  count++;
  return indexOf(ch, str.Substring(1));  //General Case
}

- manish

---

使用静态变量并不是一个好主意。这也存在一个偏移一位的错误，如果字符串中不包含所请求的字符，则会产生完全错误的结果。 - JLRishe

@JLRishe 根据您的指示，我已经修复了“字符不存在”的情况，并且我使用了静态变量，只是因为我不想改变用户函数的原型（即使用额外的参数）。无论如何，感谢您的评论。 - manish