文字列中の 'x'文字の数 - 再帰

Question

私はJavaでかなりの基本的な再帰問題を練習しています。

public int countX(String str) { 
     if (str == null || str.length() == 0) 
     return 0; 
     else if (str.length() == 1) 
     return str.charAt(0) == 'x' ? 1 :0; 
     else { 
     return (str.charAt(str.length()-1) == 'x' ? 1 : 0) + countX(str.substring(0,str.length()-1)); 
     } 
    } 

これは正常に動作します -

countX("xxhixx") → 4 

countX("xhixhix") → 3 

countX("hi") → 0 

"という文字列を考えると、文字列内の小文字の 'はx' の文字の数を再帰的に（何のループ）を計算していません"。しかし、私はそれを書く良い方法があるかどうかを知りたいです。私はこのコードが単純な問題のために複雑であることを知っています。

Answer 1

これは厄介な主な理由です。再帰的な解法は、文字列や配列の中のものを数えるのに、一般的に最適ではありません。少なくとも私にとってはコードが奇妙に見えますが、実際にはすべての文字に対して新しいスタックフレームと新しいバージョンの文字列を作成しています。これは非効率的です（String.substringが完全なコピーを作成するのではなく元のバッファを指すように最適化されているかどうかは疑問ですが、文字列は不変です）。

しかし、あなたの問題の制約を与え、あなたはおそらく、あなたのコード内で行う少数の冗長チェックを取り除くことができます：あなたはすでにnullと空の文字列の文字列をテストするので

public int countX(String str) { 
    if(str == null || str.isEmpty()) 
     return 0; 
    return (str.charAt(0) == 'x' ? 1 : 0) + countX(str.substring(1)); 

長さ1はもはや特殊なケースではない。

最後の文字ではなく、各繰り返しで最初の文字を削除することで、インデックス作成とsubstringの呼び出しをもっときれいにすることができます。これにより、str.length()への2つの明示的な呼び出しも削除されます。この条件は、すでにreturn (str.charAt(...

によって処理されている私は、それはそれ以上に向上することができるとは思わないよう

Answer 2

長さ1の文字列のための特別な処理が冗長である - それは、すでにelse句によってカバーされています：

public int countX(String str) { 
    if (str == null || str.length() == 0) 
     return 0; 
    } 
    return (str.charAt(str.length()-1) == 'x' ? 1 : 0) + 
      countX(str.substring(0,str.length()-1)); 
} 

Answer 3

これは、より明確に見えますか？

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

Answer 4

else if (str.length() == 1)は必要ありません。実際には、問題は再帰を使用するにはあまりにも単純だと思います（ループを使用するとかなり簡単になりますが、使用することはできません）...とにかく必要以上に複雑なコードになります。

Answer 5

これを試してみてください：

ただ、好奇心のうち

public int countX(String str) { 
    if (str == null) 
    return 0; 
    else { 
     int occurrence = str.lastIndexOf("x"); 
     int count = occurrence > -1 ? 1 + countX(str.substring(0, occurrence)) : 0; 

     return count; 
    } 
}