在一个字符串中递归计算字符出现次数。

Question

我正在编写一个程序来计算字符串中字符出现的次数。这是我的方法：

public static int count (String line, char c)
{
    int charOccurences = 0; //= 0;

    for (int x = 0 ; x < line.length () ; x++)
    {
        if (line.charAt (x) == c)
        {
            charOccurences++;
            line = line.substring (0, x) + line.substring (x + 1);
            return count (line, c);
        }
        else
            return charOccurences;
    }
    return charOccurences;
}

这段代码总是返回0，因为一旦该方法调用自身，它就会将charOccurences重置为0。但我需要声明该变量才能使该方法正常工作。我无法想到任何解决办法。希望能得到任何帮助。

- Noob

---

一个问题是你的for循环中的else语句。此外，为什么要递归地做这个，只需循环遍历原始字符串即可。一个简单的for循环就足够了。 - Alexis C.

主要问题在于每次方法递归时，我将charOccurences设置为0。我无法想出不这样做的方法。此外，我的老师告诉我们要使其递归。 - Noob

那么你可能不需要使用循环。使用递归或循环，但不要同时使用两者。 - Alexis C.

在if语句中，应该返回charOccurrences+=count(line,c); 返回charOccurrences; 显然还有else的问题。 - Jekyll

Answer 1

在你增加了charOccurences之后，你忽略了它。

charOccurences++;
line = line.substring (0, x) + line.substring (x + 1);
return charOccurences + count (line, c); // Fixed for you.

其他人已经提到，你根本不需要一个for循环。如果你想要纯粹使用递归实现，那么你只需要去掉循环，按照以下步骤进行：

• 基本情况：
  • 第一个字符不存在（长度为零）
    • return 0;
• 递归情况：
  • 第一个字符存在
    • 如果匹配，增加出现次数
    • 否则什么也不做
    • 返回（出现次数）+（子串递归的结果）；

- Rainbolt

---

谢谢。真不敢相信我错过了那个 :p - Noob

@Noob 编辑了答案，展示了如何完全消除循环。你的代码在技术上仍然是正确的，但它每次递归时都从字符串的开头开始，这是很多额外工作。 - Rainbolt

Answer 2

是的，使用递归非常容易 :)

public static void main(String[] args) {
    String text = "This is my text. Life is great";
    System.out.println(count(text,'i',0));
}

public static int count(String line, char c, int pos) {
    if (pos >= line.length()){
        return 0;
    }

    return compare(line.charAt(pos), c) + count(line, c, pos+1);
}

public static int compare(char a, char b){
    if (a == b){
        return 1;
    } else {
        return 0;
    }
}

请注意，由于不是每次都进行子字符串操作，因此时间复杂度为O(n)，而不是您的O(n^2)。

- libik

Answer 3

以下是关于编写递归方法的一般方法，用于处理那些本不应该使用递归但因为你在课堂上学习递归而必须使用递归的任务：

找到将问题分解成更小问题的方法。在这里，您的问题是计算字符串中字符c的出现次数。好吧，假设您将字符串分解为“第一个字符”和“所有其他字符的子字符串”。您可以判断第一个字符是否等于c。然后您查看“所有其他字符”，如果它不为空（基本情况），则它只是同一问题的较小版本。因此，您可以对其使用递归。所以假装递归已经发生了，那么您就知道：（1）第一个字符是否等于c，以及（2）较小字符串中有多少个c的出现次数。一旦您知道这两个数据，您应该能够计算出整个字符串中有多少个c的出现次数。

对于这个问题，您的解决方案不应该包含循环。

- ajb

Answer 4

你实际上从未增加计数。你只是一直返回计数。在递归堆栈的最后，count将返回0，因为这是你在每个方法调用开始时初始化计数的值，并且它将一直返回零直到达到堆栈底部，然后返回0。你需要做以下事情：

charOccurences += count (line, c);
return charOccurences;

所以charOccurences将在第一次出现时从1开始，然后向上传播。

- dckuehn

Answer 5

我曾经遇到过同样的问题，你总是可以这样做，我在 Word 上做了同样的事情，对于句子也同样适用。

private static int count(String word, String letter) {
    int count = 0;
 return occurrence(word, letter, count);
}

private static int occurrence(String word, String letter, int count) {
if () 
base case 
else 
// compare and increment if it matches..
return occurrence(word.substring(0, word.length() - 1), letter,count)

} 

另一种方法是递归方法，现在您的代码中已经定义了计数器，可以增加而不会出现任何问题！ :)

- Roland

Answer 6

请在for循环中删除else循环。如果保留该循环，则应仅获取一个字符的出现次数。

public static int count (String line, char c)
{
    int charOccurences = 0; //= 0;

    for (int x = 0 ; x < line.length () ; x++)
    {
        if (line.charAt (x) == c)
        {
            charOccurences++;
            line = line.substring (0, x) + line.substring (x + 1);
            return count (line, c);
        }
    }
    return charOccurences;
}

- vishwajit dalve

---

嗨，Vishwajit，如果一个问题已经有了被接受的答案，通常就不需要再次回答它。特别是，如果这个问题在很多年前就已经被提出和回答了。如果你想要回答新的问题，请查看这里。 - devdanke

Answer 7

尽管递归不是必需的（我们只是为了好玩而这样做），但你几乎完成了。只需确保有一个停止递归的条件：在这里，它是if (len == 0)…语句。

public static int count (String line, char c)
{
    int len = line.length();
    if ((len == 0) || (c == '\0'))   // obvious case for empty string or nil char.
       return 0;                     // Your recursion always ends here

    String rest = line.substring(1);
    if (line.charAt(0) == c)     
    {
       return count(rest, c) + 1;   // recurse on substring
    }
    else
    {
       return count(rest, c);   // recurse on substring
    }
}

- Vincent Zgueb

Answer 8

我认为你正在把它变得比必要的更难？

public static int count(String line, char c) {
    int orig = line.length();
    int repl = line.replaceAll("" + c, "").length();
    return orig - repl;
}

- SiKing

---

我需要它是递归的。 - Noob

“Do my homework!” 不是原帖的一部分。 - SiKing

这实际上是一个非常优雅的解决方案，只是不是递归的。 - Fergus