java - 基本递归枚举解释

Question

我有一个简单的类，它使用带有处理函数的递归枚举来计算并最终打印 X 数量的 6 面骰子的所有可能组合。然而，虽然这个程序可以工作(使用找到的算法进行枚举过程)，但我并不完全确定递归到底在做什么，以允许类对所有可能性进行排序。

main方法直接调用枚举，

enumerate(N, 0, new int[N]);

枚举方法非常简单，

    public static void enumerate(int N, int k, int[] a) {
    if (k == N) {
        process(a);
        return;
    }
    for (int i = 0; i < 2; i++) {
        a[k] = i;
        enumerate(N, k + 1, a);
    }
}

此时有效调用的 process 方法不执行任何操作，只是打印传递给它的数组

    public static void process(int[] a) {
    for (int i : a) {
        System.out.print(i);
    }
    System.out.println();
}

TL;DR - 我有一个枚举方法，当 k==n 时，它似乎返回 - 也就是说，完整的可能性数组已完成。但是，该类返回所有可能的组合。递归函数到底做了什么才使得这成为可能？为什么在形成完整组合后，枚举方法返回时程序没有停止？

Answer 1

您在该程序中看到的递归类型让我想起了二叉树。

如果您观察变量 k 和 i 的值，并在使用调试器执行程序期间跟踪其值，则可以构建二叉树。如果我们考虑表达式 (k, i)，您可以看到这段代码的执行创建了下面的递归树:

int[] a = new int[3];
enumerate(a.length, 0, a);

这是生成的树，其值为(k, i):

                      (0, 0)
         (1, 0)                      (1, 1)
    (2, 0)    (2, 1)             (2, 0)   (2, 1)
(3, 0) (3, 1) (3, 0) (3, 1) (3, 0) (3, 1) (3, 0) (3, 1)  

如果您随后使用深度优先搜索从 (1, 0) 和 (1, 1) 节点遍历树，您可以通过沿着遍历路径收集 i< 的值来重建打印出来的值.

使用DFS遍历的结果正是控制台应该打印出来的结果:

000 - (1, 0)(2, 0)(3, 0)
001 - (1, 0)(2, 0)(3, 1)
010 - (1, 0)(2, 1)(3, 0)
011 - (1, 0)(2, 1)(3, 1)
100 - (1, 1)(2, 0)(3, 0)
101 - (1, 1)(2, 0)(3, 1)
110 - (1, 1)(2, 1)(3, 0)
111 - (1, 1)(2, 1)(3, 1)