Java 递归计算字符串中的字符出现次数

Recursively counting character occurrences in a string

提问by Noob

Im making a program to count the number of times a character is found in a string. This is what my method looks like:

我正在制作一个程序来计算在字符串中找到一个字符的次数。这是我的方法的样子：

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

It always returns 0, due to the fact that once the method calls itself it sets charOccurencesback to 0. But i need to declare that variable for the method to work. I cant figure any way around this. Any help would be appreciated.

它总是返回 0，因为一旦该方法调用自身，它就会设置charOccurences回 0。但我需要声明该变量才能使该方法工作。我想不出任何办法解决这个问题。任何帮助，将不胜感激。

采纳答案by Rainbolt

You ignored charOccurences right after you incremented it.

您在增加 charOccurences 后立即忽略了它。

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

Others have mentioned that you don't need a for loop at all. If you wanted to do this purely recursively, you would simply lose the loop, and follow these steps:

其他人提到您根本不需要 for 循环。如果您只想以递归方式执行此操作，则只会丢失循环，然后执行以下步骤：

• base case:
  • first character doesn't exist (length is zero)
    • return 0;
• recursion case:
  • The first character does exist
    • if it matches, increment occurrences
    • else do nothing
    • return (occurrences) + (result of recursing with substring);

• 基本情况：
  • 第一个字符不存在（长度为零）
    • return 0;
• 递归案例：
  • 第一个字符确实存在
    • 如果匹配，则增加出现次数
    • 别的什么都不做
    • return (occurrences) + (substring 递归的结果);

回答by dckuehn

You never actually increment count. You just keep returning count. At the very end of your recursive stack, count will return 0, as that is what you initialize count to at the begining of every method call, and it will keep returning zero until it gets to the bottom of the stack, then return 0. You need to do this:

你从来没有真正增加计数。你只是不断地返回计数。在递归堆栈的最后，count 将返回 0，因为这是您在每个方法调用开始时初始化 count 的值，并且它将一直返回零，直到到达堆栈底部，然后返回 0。你需要这样做：

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

so charOccurences will start at 1 at the first occurence, then propagate up.

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

回答by libik

Yea, it is very easy to do it recursively :)

是的，递归地做到这一点很容易:)

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

Note that thanks to not substringing every time, time complexity is O(n) instead of yours O(n^2)

请注意，由于不是每次都进行子串，时间复杂度是 O(n) 而不是你的 O(n^2)

回答by Vincent Zgueb

Despite doing it recursively is not required (let's do it for fun). You were almost done. Just be sure to have a condition that stops the recursion: here it is if (len == 0)…statement.

尽管不需要递归执行（让我们为了好玩而这样做）。你快完成了。只要确保有一个停止递归的条件：这里是if (len == 0)…语句。

public static int count (String line, char c)
{
    int len = line.length();
    if ((len == 0) || (c == '
public static int count(String line, char c) {
    int orig = line.length();
    int repl = line.replaceAll("" + c, "").length();
    return orig - repl;
}
'))   // 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
    }
}

回答by ajb

Here's a general approach for writing recursive methods for tasks that really shouldn't be recursive but have to be because you're learning about recursion in class:

这是为真正不应该递归但必须递归的任务编写递归方法的一般方法，因为您正在课堂上学习递归：

Find a way to break the problem down into a smaller problem(s).

找到将问题分解为较小问题的方法。

Here, your problem is to count the occurrences of character cin a string. Well, suppose you break your string down into "the first character" and a substring of "all the other characters". You can tell whether the first character equals c. Then you look at "all the other characters", and if that's not empty (the base case), then that's just a smaller version of the same problem. So you can use recursion on that. So pretend the recursion already happened, so then you know: (1) is the first character equal to c, and (2) how many occurrences of care there in the smaller string. Once you know those two pieces of data, you should be able to figure out how many occurrences of cthere are in the whole string.

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

For this problem, your solution should not have a loop in it.

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

回答by SiKing

I think you're making it much harder than it needs to be?

我认为你让它变得比它需要的要困难得多？

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)

} 

回答by Roland

i had the same issue you can always do this i did it on a word same applies for a sentence

我遇到了同样的问题，您可以随时执行此操作

##代码##

the other method occurrence be the recursion method, and repeat your code now count is already defined and you can increment without having any problem! :)

另一个方法是递归方法，现在重复你的代码 count 已经定义，你可以增加而没有任何问题！:)