问题在理解递归 - 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

回答

相关问题