理解递归时遇到的问题 - Java

Question

我从 this 问题中获取了代码，我在 Eclipse 中运行了它，代码很好，但是我对递归顺序内部如何进行感到困惑。

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));

            }
        }
    }
}

我发现很难理解 Shuffle 的 for 循环中的递归。有解码递归步骤的指针吗？

编辑：好的，这是我的理解，假设我的输入是 ABC ，当我在第一个循环中运行时，我得到虚拟 = A 和输入 = BC ，所以立即采取的步骤是沿着输入 = BC 和虚拟 = A 的递归，然后返回迭代 i 以获取初始输入？

Answer 1

添加全局计数器：

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", "");

运行程序。现在您可以看到会发生什么。

Answer 2

将其视为将工作分成步骤。您的 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);

然后，递归地应用算法，已经洗牌的部分会更长：

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

直到不再需要洗牌：

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

Answer 3

它递归地按输入长度彻底混洗输入。因此，一旦每次递归将字符串打乱第 i 个项后，它就会返回。

这将是一个采用大 O 表示法的 n 平方复杂度算法。

如果没有调试器，改组是很棘手的；）