CODEWITHSUNDEEP
javarecursionenumeration
HunterM267
HunterM267

Reputation: 309

Basic recursive enumeration explanation

I have a simple class that computes and ultimately prints all possible combinations of X amount of 6-sided die, using recursive enumeration with a process function. However, while this program works (using found algorithms for the enumeration process), I'm not entirely certain what exactly the recursion is doing that allows the class to sort through ALL possibilities.

The main method is calling the enumeration directly,

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

The enumeration method is quite straightforward,

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

The process method that is called effectively does nothing at this point, and just prints the array that's passed to it

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

TL;DR - I have an enumerate method that seemingly returns when k==n - that is, a complete array of possibilities is complete. However, the class returns all possible combinations. What exactly is the recursive function doing that allows this to be possible? Why doesn't the program stop when the enumerate method is returned after forming a complete combination?

Upvotes: 0

Views: 1404

Answers (1)

gil.fernandes
gil.fernandes

Reputation: 14611

The type of recursion you see in this programme reminds me of a binary tree.

If you observe the values of the variables k and i and follow its values during the execution of the programme with a debugger, you can build a binary tree. If we consider the expression (k, i) you can see that the execution of this piece of code creates this recursion tree below:

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

This is the resulting tree with the values (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)

If you then traverse the tree using depth first search from the (1, 0) and (1, 1) nodes you can reconstruct the values which are printed out by gathering down the traversal path the values of i.

The traversal result using DFS is exactly the result which should be printed out on the console:

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)

Upvotes: 2

Related Questions