如何遞歸計算字符串中某些特定字符的數量？

Question

我在練習遞歸問題。有一些類型的問題要求您計算沒有循環的String中特定字符的數量。

我應該使用什麼樣的方法？任何人都可以向我解釋？

下面是一個問題：「給定一個字符串，遞歸計算（無循環）字符串中小寫'x'字符的數量。

我的代碼：

public int countX(String str) { 
    if(str.length()==0){ 
     return 0; 
    } 
    if(str.charAt(0)=='x'){ 
     return 1+ countX(str.substring(1)); 
    } 
    return countX(str); 
} 

Answer 1

就快，但你需要修改的情況下在str的第一個字母是不是'x'。您目前正在做的操作將導致無限遞歸，因爲在str.charAt(0) != 'x'的情況下，您遞歸地調用str上的countX。然而，str仍然是第一個字母沒有'x'的字符串，所以它會一次又一次地在str上調用countX等。所以解決方法是在str.substring(1)的第一個字母時僅調用countX是不是'x'像這樣，

public int countX(String str) { 
    if(str.length()==0){ 
     return 0; 
    } 
    if(str.charAt(0)=='x'){ 
     return 1 + countX(str.substring(1)); 
    } 
    else{ 
     return countX(str.substring(1)); 
    } 
} 

你的方法之前

做比方說，我在"Hello"叫countX，這裏的調用堆棧跟蹤會是什麼樣子，

call countX("Hello") 
"Hello".length() != 0 so we move on to the next condition 
"Hello".charAt(0) != 'x' so we call countX("Hello") 
    call countX("Hello") 
    "Hello".length() != 0 so we move on to the next condition 
    "Hello".charAt(0) != 'x' so we call countX("Hello") 
     call countX("Hello") 
     "Hello".length() != 0 so we move on to the next condition 
     "Hello".charAt(0) != 'x' so we call countX("Hello"); 
      . 
      . 
      . 
      infinite recursion 

新的解決方案能做什麼

call countX("Hello") 
"Hello".length() != 0 so we move on to the next condition 
"Hello".charAt(0) != 'x' so we call countX("ello") 
    call countX("ello") 
    "ello".length() != 0 so we move on to the next condition 
    "ello".charAt(0) != 'x' so we call countX("llo") 
     call countX("llo") 
     "llo".length() != 0 so we move on to the next condition 
     "llo".charAt(0) != 'x' so we call countX("lo"); 
      call countX("lo") 
      "lo".length() != 0 so we move on to the next condition 
      "lo".charAt(0) != 'x' so we call countX("o"); 
       call countX("o") 
       "o".length() != 0 so we move on to the next condition 
       "o".charAt(0) != 'x' so we call countX(""); 
        call countX("") 
        "".length() == 0 so return 0 
       return 0 
      return 0 
     return 0 
    return 0 
return 0 

請注意，在該解決方案中，我們總能有基本案例（str.length()==0）的一種方式。而之前會有一些情況（當我們遇到不是x的字母時）會阻止該方法到達基本情況。

Answer 2

我應該使用什麼樣的方法？任何人都可以向我解釋？

一個解決方案是使用一個StringBuilder，只是在方法的每次調用刪除第一個字符，最終，你會得到基本情況和應該輸出正確的結果。

public int countX(String str) { 
     if(str.length() == 0) return 0; 

     StringBuilder builder = new StringBuilder(str); 
     if(str.charAt(0) == 'x'){ 
      builder.deleteCharAt(0); 
      return 1 + counter(builder.toString()); 
     } 

     builder.deleteCharAt(0); 
     return counter(builder.toString()); 
} 

但是，如果你想與您當前的解決方案來進行，你需要替換此：

return countX(str); 

與此：

return countX(str.substring(1)); 

的問題是，如果當前字符不是'x'，您只是忽略它，並未將問題簡化爲基本情況。

Answer 3

我瞭解您的需求。在下面，你有你需要遞歸計算字符串中的字符的方法。

static int countCharRecursively(String str, char ch){ 

    if(str.indexOf(ch) != -1) 
    {   
     return countCharRecursively(str.substring(0, str.indexOf(ch)), ch)+ 
      countCharRecursively(str.substring(str.indexOf(ch)+1),ch) + 1; 
    } 
    else{ 
     return 0; 
    } 
} 

這是一個可以運行的完整程序。

public class CountCharRecursivelyInString{ 

public static void main(String[] args){ 

    String str = "hello the world"; 

    char ch = 'l'; 

    int nbr = countCharRecursively(str, ch); 

    System.out.println(ch + " : " + nbr); 
} 

static int countCharRecursively(String str, char ch){ 

    if(str.indexOf(ch) != -1) 
    {   
     return countCharRecursively(str.substring(0, str.indexOf(ch)), ch)+ 
      countCharRecursively(str.substring(str.indexOf(ch)+1),ch) + 1; 
    } 
    else{ 
     return 0; 
    } 
} 
}