0

私は再帰が初めてで、まだこの問題と混同しています。

ここにコードがあります

 public class TestRecursion { 
 public static void main(String[] a) { 
 System.out.println(Recurse("Yes", 1)); 
 } 

 public static String Recurse(String s, int n) { 
 if (n < 5) 
 return s+Recurse(s + n, n + 1); 
 else 
 return "End"; 
 } // end Recurse() 
}

したがって、これに対する答えは次のとおりです。

YesYes1Yes12Yes123End

問題は、リターンをに切り替えたときに「終了」が最初に出力されるのはなぜですか

 return Recurse(s + n, n + 1) + s;

s が再帰の後であることに注意してください

結果は次のとおりです。

EndYes123Yes12Yes1Yes
4

3 に答える 3

1

"End" は、文字列の最後の部分が評価される場所に配置されます。最後の部分を実行するとs + recurse、最後に評価されます。startを実行recurse + sすると、最後に評価されます。

于 2013-10-27T21:08:14.310 に答える
1

仮想紙をつかんで、これを解決しましょう。

public class TestRecursion { 
  public static void main(String[] a) { 
    System.out.println(Recurse("Yes", 1)); 
  } 

  public static String Recurse(String s, int n) { 
    if (n < 5) 
      return s+Recurse(s + n, n + 1); 
    else 
     return "End"; 
  } // end Recurse() 
}

では、最初から始めます。

n     S           s+Recurse(s+n, n+1)
1     Yes         "Yes" + Recurse ("Yes1", 2)
2     Yes1        "Yes1" + Recurse ("Yes12", 3)
3     Yes12       "Yes12" + Recurse ("Yes123", 4)
4     Yes123      "Yes123" + Recurse ("Yes1234", 5)
5     Yes1234     "End" <- Here we go to the else block

したがって、スタックを展開すると、次のようになります。

n     S           s+Recurse(s+n, n+1)
5     Yes1234     "End" <- Here we go to the else block
4     Yes123      "Yes123" + "End"
3     Yes12       "Yes12" + "Yes123End"
2     Yes1        "Yes1" + "Yes12Yes123End"
1     Yes         "Yes" + "Yes1Yes12Yes123End"

したがって、最終的にはYesYes1Yes12Yes123End

それでは、メソッドを変更しましょう。

public class TestRecursion { 
  public static void main(String[] a) { 
    System.out.println(Recurse("Yes", 1)); 
  } 

  public static String Recurse(String s, int n) { 
    if (n < 5) 
      return Recurse(s + n, n + 1) + s; 
    else 
     return "End"; 
  } // end Recurse() 
}

では、最初から始めます。

n     S           Recurse(s+n, n+1) + s
1     Yes         Recurse ("Yes1", 2) + "Yes"
2     Yes1        Recurse ("Yes12", 3) + "Yes1"
3     Yes12       Recurse ("Yes123", 4) + "Yes12"
4     Yes123      Recurse ("Yes1234", 5) + "Yes123"
5     Yes1234     "End" <- Here we go to the else block

スタックを展開すると、次のようになります。

n     S           Recurse(s+n, n+1) + s
5     Yes1234     "End" <- Here we go to the else block
4     Yes123      "End" + "Yes123"
3     Yes12       "EndYes123" + "Yes12"
2     Yes1        "EndYes123Yes12" + "Yes1"
1     Yes         "EndYes123Yes12Yes1" + "Yes"

だから、私たちは最終的に得るEndYes123Yes12Yes1Yes

于 2013-10-27T21:14:41.633 に答える
1

再帰は、ツリー構造 (いわゆる再帰ツリー) で最もよく視覚化できることに注意してください。通常、端末 (この場合はs) と非端末 (さらなる関数呼び出し、つまりRecurse) があります。draw.io (ウェブサイト) を使用して、次のケースを説明するためにこの図をすばやく作成しましたRecurse(s + n, n + 1) + s。

再帰木

常に左から右に評価します。各ステップで終端と非終端の順序を入れ替えるとどうなるかを確認するには: 画像を垂直方向にミラーリングし、左から右に再度評価します。

于 2013-10-27T21:26:34.843 に答える