java - JAVA: 再帰関数の修正を支援

Question

この問題には再帰を使用する必要があります。ループを使用してかなり迅速に機能させることができましたが、これには少し行き詰まっています。私の現在のコードは

public static String ReverseR(String n){
    String finalstring="";
    int i = 0;
    int len = n.length();
    while (i < len) {
        finalstring += (n.charAt(len -  1));
        ReverseR(n.substring(0, len - 1));
        i++;
    }
    return finalstring;
}

文字列を入力すると、結果の文字列は正しい長さになりますが、最後の文字のみが使用されます。例: ReverseR("Hello") = ooooo 何かアイデアはありますか?

score 5 · Accepted Answer

再帰は帰納法による証明のようなものです。

while ループを取り除く
0 文字の文字列を反転する場合は簡単です。"" を返すだけです。
n 文字の文字列を反転する場合は、[0..n-2] を反転し、最後の文字を先頭に追加します。あなたはすでにやっています。

score 1 · Accepted Answer

n.charAt(len - 1))に変更n.charAt(len - i))

あなたはいつもlen -1と同じ場所にいます;）

[編集]

while (i < len){
    finalstring += (n.charAt(len - 1 - i));
    ReverseR(n.substring(0, len - 1 - i));
    i++;
}

これでコードが修正されますが、whileまたはどちらかを選択する必要がありますReverseR(...)

重複した質問、これを確認してくださいJavaでの再帰を使用した文字列の反転

score 0 · Accepted Answer

while再帰アルゴリズムは、ループ、つまりandループを必要としませんfor。ループ構造は基本的に、ループに触れることなく再帰によって実装できます。基本的な再帰的な文字列反転の例は、次のようになります。

public static String reverseR(String n){
  if (n.length() <= 1) return n;
  return reverseR(n.substring(1))+n.charAt(0);
}

このアルゴリズムでは、基本的に次のように言っています: 「最初の文字を除くすべての文字の反転」+「最初の文字」を返す

再帰アルゴリズムを書く上で役立つ良いことは、多くの仮定を立てることです。最初に逆関数が機能すると仮定してから、文字列の一部を逆にしたい場所にそれを配置します。ベースケースを追加することを忘れないでください。言語は、再帰アルゴリズムが反復の主なソースであるため、再帰アルゴリズムに慣れますHaskell。Prolog

score 0 · Accepted Answer

ここに完全な実用的なソリューションがあります

public static String reverse(final String s) {
    if (s == null) {
        throw new NullPointerException();
    }

    final int length = s.length();
    if (length <= 1) {
        return s;
    } else {
        // s = start + lastChar
        final String start = s.substring(0, length - 1); 
        final char lastChar = s.charAt(length - 1);
        return lastChar + reverse(start);
    }
}

java - JAVA: 再帰関数の修正を支援

4 に答える 4

Related

Reference