在字符串中递归查找字符 [英] Find a character recursively in a String

问题描述

这是来自弗吉尼亚理工大学的openDSA交互式学习平台中的一个问题：

This is a question in the openDSA interactive learning platform from Virginia Tech:

对于函数 countChr，请写出缺少的部分递归调用。
此函数应返回字母 A
在字符串 str中出现的次数。

For function "countChr", write the missing part of the recursive call. This function should return the number of times that the letter "A" appears in string "str".

int countChr(String str) {
  if (str.length() == 0) {
    return 0;
  }
  int count = 0;
  if (str.substring(0, 1).equals("A")) {
    count = 1;
  }
  return count + <<Missing a Recursive call>>
}

我知道如何通过以下方式非递归地找到字符：

I know how to find a character non recursively in the following way:

 public static void main(String [] args) {
      String str ="abdcfghaasdfaadftaxvvaacvbtradcea";
      int count =0;
      for(int n=0; n<= str.length()-1; n++) {
      if(str.charAt(n)== 'a')
          count++;
      }
      System.out.print(count);
  }

我真的不知道如何递归地做同样的事情，尤其是在

I really don't know how to do the same recursively, especially following the exact pattern given in the question.

推荐答案

要递归获取字母 A的出现次数，您需要递归调用带有从索引1到字符串结尾的子字符串的函数：

To recursively obtain the number of occurrences of the letter 'A', you need to recursively call the function with the substring from index 1 to the end of the string:

public class Example {

    public static void main(String [] args) {
        String str ="abdcfghaasdfaadftaxvvaacvbtradcea";
        System.out.println(countChr(str));

        String str2 ="abdcfAhaasdAaadftaxvAAAacvbtradcea";
        System.out.println(countChr(str2));
    }

    static int countChr(String str) {
        if (str.length() == 0) {
            return 0;
        }
        int count = 0;
        if (str.substring(0, 1).equals("A")) {
            count = 1;
        }
        return count + countChr(str.substring(1));
    }
}

输出：

0
5

解释其工作原理：

• 该函数首先用整个String调用


• 字符串长度为0，因为不会出现'A'，所以返回0。


• 将计数器初始化为0，该计数器将用于计数出现的次数。


• 如果字符串的第一个字符为'A'，则增加计数器


• 现在要重复此过程，我们需要使用相同的String调用相同的函数，除非没有第一个字符。我们将此递归调用的结果添加到计数器中并返回。

• The function is first called with the entire String
• If the String length is 0 return 0 because there cannot be an occurrence of 'A'
• Initialise a counter to 0, which will be used to count the number of occurrences.
• If the first character of the String is 'A' increment the counter
• Now to repeat this process, we need to call the same function with the same String, except without the first character. We add the result of this recursive call to the counter, and return it.

此过程可以通过添加一些打印件来说明：

This process can be illustrated by adding some prints:

 int countChr(String str) {
        System.out.println(str);
        if (str.length() == 0) {
            System.out.println("String has length 0, returning 0");
            return 0;
        }
        int count = 0;
        if (str.substring(0, 1).equals("A")) {
            System.out.println("Character is an 'A' adding 1 to the count");
            count = 1;
        }
        return count + countChr(str.substring(1));
}

输出：

abdcfAhaasdAaadftaxvAAAacvbtradcea
bdcfAhaasdAaadftaxvAAAacvbtradcea
dcfAhaasdAaadftaxvAAAacvbtradcea
cfAhaasdAaadftaxvAAAacvbtradcea
fAhaasdAaadftaxvAAAacvbtradcea
AhaasdAaadftaxvAAAacvbtradcea
Character is an 'A' adding 1 to the count
haasdAaadftaxvAAAacvbtradcea
aasdAaadftaxvAAAacvbtradcea
asdAaadftaxvAAAacvbtradcea
sdAaadftaxvAAAacvbtradcea
dAaadftaxvAAAacvbtradcea
AaadftaxvAAAacvbtradcea
Character is an 'A' adding 1 to the count
aadftaxvAAAacvbtradcea
adftaxvAAAacvbtradcea
dftaxvAAAacvbtradcea
ftaxvAAAacvbtradcea
taxvAAAacvbtradcea
axvAAAacvbtradcea
xvAAAacvbtradcea
vAAAacvbtradcea
AAAacvbtradcea
Character is an 'A' adding 1 to the count
AAacvbtradcea
Character is an 'A' adding 1 to the count
Aacvbtradcea
Character is an 'A' adding 1 to the count
acvbtradcea
cvbtradcea
vbtradcea
btradcea
tradcea
radcea
adcea
dcea
cea
ea
a

String has length 0, returning 0

这篇关于在字符串中递归查找字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！