基本递归枚举解释

Question

我有一个简单的 class，它使用带有过程函数的递归枚举计算并最终打印出 X 数量的 6 面骰子的所有可能组合。然而，虽然这个程序有效（使用找到的算法进行枚举过程），但我不完全确定递归到底做了什么允许 class 对 ALL 进行排序可能性。

主要方法是直接调用枚举，

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

有效调用的处理方法此时什么都不做，只是打印传递给它的数组

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

TL;DR - 我有一个枚举方法，当 k==n 时似乎 returns - 也就是说，完整的可能性数组是完整的。然而，classreturns所有可能的组合。递归函数究竟做了什么使这成为可能？为什么在形成完整组合后返回枚举方法时程序不停止？

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) 节点遍历树，您可以重建通过收集遍历路径 [=14 的值打印出的值=].

使用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)

基本递归枚举解释

Basic recursive enumeration explanation

java

recursion

enumeration