2 
//method
public static String foo(String s)

{
if (s.length() == 1)

return s;

else

return foo(s.substring(1)) + s.charAt(0);
}

foo(“abcd”) は何に評価されますか? これが入力を逆にすることは私の理解ですが、それはなぜですか?

4

3 に答える 3

3

ここで再帰に直面しています！

再帰の各レベルは、最初の文字を最後に追加し、文字列のサフィックスで再帰呼び出しを呼び出します。

あなたの例では、コール スタックは次のようになります。

s = "abcd" => append 'a' to the end, and invoke on "bcd".
s = "bcd" => append 'b' to the end, and invoke on "cd".
s = "cd" => append 'c' to the end, and invoke on "d".
s= = "d" => return "d" as it is.

再帰から戻るときは、実際には逆の順序で追加します。

return "d"
return "d" + 'c' (="dc")
return "dc" + 'b' (="dcb")
return "dcb" + 'a' (="dcba")
于 2012-05-01T13:49:14.333 に答える
3

この場合、再帰がどのように機能するかが明確になることを願っています。

foo("bcd") + "a"
  (foo("cd") + "b") + "a"
    ((foo("d") + "c") + "b") + "a"
      (("d" + "c") + "b") + "a" -> "dcba"
于 2012-05-01T13:51:18.290 に答える
3

再帰的な逆です。s.substring(1)最初の文字がない行です。s.charAt(0)最初の文字です。

関数が言っているのは、「行の長さが 1 文字の場合、答えは行自体です。それ以外の場合は、最初の文字を切り捨て、同じ関数を計算し、切り捨てられた文字を結果の最後に追加します」。

上記の手順を実行すると、文字列を逆にする方法を紙に書き出すことができます。

編集:空の文字列を渡そうとすると、この実装は例外でクラッシュすることに注意してください。に変更if (s.length() == 1)するif (s.length() == 0)と、この問題に対処できます (コメントでこれについて言及してくれた Tom Hawtin に感謝します)。

于 2012-05-01T13:51:33.630 に答える