再帰を使用してJavaで部分文字列の出現を数えるにはどうすればよいですか？

Question

再帰を使用して、Javaで大きな文字列の部分文字列の出現を数える必要があります。私は再帰のアイデアを得るが、私はこのような問題にどのように適用されるのか分からない。誰もこれを行う方法を知っていますか？

私にも同様の問題がたくさんあります。再帰的に一般的な問題を解決するためのアドバイス？私の最大の関心事は基本事例を見つけることです。

ありがとうございます！

Answer 1

本当に一般的な方法はありませんが、私はそうは考えていません。しかし、ここで私はこの問題のためにそれをやっています：

あなたは実際に再帰（Javaでは、少なくとも）を使ってこの問題を解決しません。あなたはこのような何かを書きたい：うまくいけば、あなたはループと再帰的なアプローチの間の共通性を見ることができます

int countOccurrences(String str, String search) { 
    return recurse(str, search, 0, 0); 
} 

int recurse(String str, String search, int count, int i) { 
    i = str.indexOf(search, i); 
    if (i == -1) { 
    // Like the while loop where i == -1, i.e. no more occurrences found. 
    // Break the recursion. 
    return count; 
    } else { 
    // Like the while loop where i != -1: an occurrence was found. 
    // Increment count, and keep on searching. 
    return recurse(str, search, count + 1, i + search.length()); 
    } 
} 

：

int countOccurrences(String str, String search) { 
    int count = 0; 
    int i = 0; 
    while (true) { 
    i = str.indexOf(search, i); 
    if (i == -1) { 
     break; 
    } else { 
     count += 1; 
     i += search.length(); 
    } 
    } 
    return count; 
} 

だから、あなたは、末尾再帰などのようなものを、これを書き換えることができます。あなたは尾再帰を記述する必要はありません

注：recurseメソッドからcountパラメータを落とし、非端子ケースを作ることによって非末尾再帰を書き込むことができます。

return 1 + recurse(str, search, i + search.length()); 

テールコールの最適化を実行しないJavaではあまり違いはありませんが、テール再帰形式は他の言語ではより効率的です（上記のようにループに戻すことができます） 。