我不理解这个递归程序

Question

我有这段代码，它使用递归来获得输入的任何字符串的每种可能的字符组合。但是我不明白当程序运行时会发生什么！有人能解释一下这个程序中发生了什么吗？我还是一个编程新手，所以如果你的解释不太复杂，我将不胜感激，谢谢！

public class WordJumble {
  public static void main(String[] args) {
    String letters = "WORD";
    jumbleWords(letters, "");
  }

  //input parameters
  //word - the remaining letters in the word still to jumble
  //jumbLet - the letters already used to create the jumbled word

  public static void jumbleWords(String word, String jumbLet) {
    int pos;
    String remainingLetters;
    String origWord = word;
    String origJumbledLetters = jumbLet;
    if (word.length() == 1) 
      System.out.println(jumbLet + word);
    else {
      for (pos = 0; pos < origWord.length(); pos++) {
        remainingLetters = origWord.substring(0, pos) + origWord.substring(pos + 1, origWord.length());
        //recursive call to jumbleWords()
        jumbleWords(remainingLetters, origJumbledLetters + origWord.charAt(pos));
      }
    }
  }
}

然后输出为：

WORD
WODR
WROD
WRDO
WDOR
WDRO
OWRD
OWDR
ORWD
ORDW
ODWR
ODRW
RWOD
RWDO
ROWD
RODW
RDWO
RDOW
DWOR
DWRO
DOWR
DORW
DRWO
DROW

谢谢你的帮忙!

Answer 1

这个递归算法所做的是:接受初始字符串"WORD“

然后一次移动一个字符，一旦该字符被移动，它就会跟踪哪些子字符串已经创建，哪些字符没有移动。它将它传递回它自己，以重新混淆这个单词。

pos+1将字符项移动到字符串的下一个位置

Answer 2

如果您打印出递归调用，并添加一个额外的参数来记忆递归深度(并转换为制表符)，您可以很好地观察到发生了什么：

public class WordJumble {
  public static void main(String[] args) {
    String letters = "WORD";
    jumbleWords(letters, "", 0);
  }

  //input parameters
  //word - the remaining letters in the word still to jumble
  //jumbLet - the letters already used to create the jumbled word

  public static void jumbleWords(String word, String jumbLet, int recursionDepth) {
    int pos;
    String remainingLetters;
    String origWord = word;
    String origJumbledLetters = jumbLet;

    String tabs = "";
    if(recursionDepth > 0) { // translate recursionDepth to tab-characters
        tabs = String.format("%0" + recursionDepth + "d", 0).replace("0","\t");
    }

    if (word.length() == 1) 
      System.out.println(tabs + jumbLet + " + " + word);
    else {
      for (pos = 0; pos < origWord.length(); pos++) {
        remainingLetters = origWord.substring(0, pos) + origWord.substring(pos + 1, origWord.length());
        //recursive call to jumbleWords()
        System.out.println(tabs + "jumbleWords("+remainingLetters+", "+origJumbledLetters + " + " + origWord.charAt(pos) + ");");
        jumbleWords(remainingLetters, origJumbledLetters + origWord.charAt(pos), recursionDepth + 1);
      }
    }
  }
}

输出为：

jumbleWords(ORD,  + W);
    jumbleWords(RD, W + O);
        jumbleWords(D, WO + R);
            WOR + D
        jumbleWords(R, WO + D);
            WOD + R
    jumbleWords(OD, W + R);
        jumbleWords(D, WR + O);
            WRO + D
        jumbleWords(O, WR + D);
            WRD + O
    jumbleWords(OR, W + D);
        jumbleWords(R, WD + O);
            WDO + R
        jumbleWords(O, WD + R);
            WDR + O
jumbleWords(WRD,  + O);
    jumbleWords(RD, O + W);
        jumbleWords(D, OW + R);
            OWR + D
        jumbleWords(R, OW + D);
            OWD + R
    jumbleWords(WD, O + R);
        jumbleWords(D, OR + W);
            ORW + D
        jumbleWords(W, OR + D);
            ORD + W
    jumbleWords(WR, O + D);
        jumbleWords(R, OD + W);
            ODW + R
        jumbleWords(W, OD + R);
            ODR + W
jumbleWords(WOD,  + R);
    jumbleWords(OD, R + W);
        jumbleWords(D, RW + O);
            RWO + D
        jumbleWords(O, RW + D);
            RWD + O
    jumbleWords(WD, R + O);
        jumbleWords(D, RO + W);
            ROW + D
        jumbleWords(W, RO + D);
            ROD + W
    jumbleWords(WO, R + D);
        jumbleWords(O, RD + W);
            RDW + O
        jumbleWords(W, RD + O);
            RDO + W
jumbleWords(WOR,  + D);
    jumbleWords(OR, D + W);
        jumbleWords(R, DW + O);
            DWO + R
        jumbleWords(O, DW + R);
            DWR + O
    jumbleWords(WR, D + O);
        jumbleWords(R, DO + W);
            DOW + R
        jumbleWords(W, DO + R);
            DOR + W
    jumbleWords(WO, D + R);
        jumbleWords(O, DR + W);
            DRW + O
        jumbleWords(W, DR + O);
            DRO + W