問題在理解遞歸 - Java

我從this得到的代碼問題，我在Eclipse中運行它並且代碼很好，但是我很困惑自己如何在遞歸順序內部進行。問題在理解遞歸 - Java

public class Permute { 
    public static void main(String[] args) throws IOException { 
     System.out.println("Enter a string"); 
     BufferedReader bufReader = new BufferedReader(new InputStreamReader(
       System.in)); 
     String text = bufReader.readLine(); 
     shuffle("", text); 
    } 

    public static void shuffle(String dummy, String input) { 
     if (input.length() <= 1) 
      System.out.println(dummy + input); 
     else { 
      for (int i = 0; i < input.length(); i++) { 
       input = input.substring(i, i + 1) + input.substring(0, i) 
         + input.substring(i + 1); 
       shuffle(dummy + input.substring(0, 1), input.substring(1)); 

      } 
     } 
    } 
}

我發現在for循環Shuffle理解遞歸困難。任何指針在解碼遞歸步驟？

編輯：好吧，這是我的理解，說想我的輸入是ABC，當我在第一循環中運行，我得到啞= A，並輸入= BC，所以眼前的步驟將是往下走的遞歸對於輸入= BC和虛擬= A，然後回來迭代我的初始輸入？

來源

2011-04-10 SuperMan

將跟蹤調用與實際參數一起隨機播放，並且您將下架。 – Ingo 2011-04-10 20:56:43

可能的重複：http://stackoverflow.com/questions/717725/understanding-recursion（它可能會幫助你閱讀第一個） – 2011-04-10 21:00:06

@ z7sg：不，我很好的遞歸我只想確保我在想 – SuperMan 2011-04-10 21:04:45

添加全局計數器：

static int depth = 0; /* calling depth of the recursive method */

添加爲shuffle第一行：

System.out.printf("%" + depth++ + "s call dummy='%s' input='%s'\n", "", dummy, input);

添加作爲最後一行shuffle：

System.out.printf("%" + --depth + "s return\n", "");

運行該程序。現在你可以看到會發生什麼。

來源

2011-04-10 21:16:47

@Roland我得到Unkown格式錯誤？ – SuperMan 2011-04-10 21:31:16

這很奇怪。有關錯誤消息的任何詳細信息？我使用Sun JDK 1.6.0_20測試了它，它工作正常。 – 2011-04-10 22:24:35

異常在線程「主」 java.util.FormatFlagsConversionMismatchException：轉化率= S，標誌= 0 \t在的java.util.Formatter $ FormatSpecifier.failMismatch（未知來源） \t在的java.util.Formatter $ FormatSpecifier.checkBadFlags（未知源） \t at java.util.Formatter $ FormatSpecifier.checkGeneral（Unknown Source） \t at java.util.Formatter $ FormatSpecifier。（未知來源） \t在java.util.Formatter.parse（未知來源） \t在java.util.Formatter.format（未知來源） \t在java.io.PrintStream.format（未知來源） \t在java.io.PrintStream.printf（Unknown Source） – SuperMan 2011-04-10 22:25:37

把它看作是分步分工。您的shuffle函數有兩個參數，dummy表示已被混洗的字符串部分，input表示仍然需要混洗的部分字符串。

每走一步，你洗牌的input的第一個字符：

 for (int i = 0; i < input.length(); i++) { 
      input = input.substring(i, i + 1) + input.substring(0, i) 
        + input.substring(i + 1);

然後，遞歸的使用algorhythm，與零件已經改組爲一個字符長：

  shuffle(dummy + input.substring(0, 1), input.substring(1));

直到有無非是洗牌：

if (input.length() <= 1) 
     System.out.println(dummy + input);

來源

2011-04-10 21:08:50 ninjalj

是的，我是這樣做的。所以我回來增加我的初始輸入權？ – SuperMan 2011-04-10 21:10:49

@SuperMan：將遞歸調用看作是一個黑盒子，它在長度輸入上執行algorhythm - 1.如果你知道這個，它就類似於數學歸納的思維。 – ninjalj 2011-04-10 21:14:03

它徹底洗牌由輸入長度遞歸地輸入。因此，一旦每次遞歸都按i'th術語對字符串進行了整理，它就會返回。

這將是一個大O符號的n平方複雜度算法。

的洗牌是棘手的工作，出不調試;）

來源

2011-04-10 21:16:22 Alex

問題在理解遞歸 - Java

回答

相關問題