So I'm working on this app, and one class has a recursive subroutine that seams to be broken.

I have a class that have 4 special member variables, with 3 possible values for each member. The aforementioned function is supposed to generate a unique object (stored in an array) for every possible object permutation.

Here is what the code looks like:

private void generate(int one, int two, int three, int four) {
    if (one == 3 || two == 3 || three == 3 || four == 3) {
        return;
    }

    generate(one+1, two,   three,   four);
    generate(one,   two+1, three,   four);
    generate(one,   two,   three+1, four);
    generate(one,   two,   three,   four+1);

    arrayList.add(new Permu(one, two, three, four));
}

Now before anyone gives me flack for using ArrayList, I'm going to be constantly removing stuff from there later.

Anyway, now before I tell you what's going on here, you should first know that I wrote the same code in processing (instead of creating a new class it just outputs the permutation so I can see it's done) and this (almost) exact code worked just fine. That said, have a look at what the output from Android Studio is when you try and run this code on Android

0000
1000
2000
2100
2200
2210
2220
2221
2222
2211
2221
2222
2212
2222
2201
2211
2221
2222

And it continues this pattern until it runs out of memory and crashes (in Android Emulator). No stack overflow or anything.

Any insight into this would be very much appreciated. Thank you in advance.

PS. Going to try use nested loops in the mean time

1 Answers

0
Stefan On

Even if you get rid of your infinite loop your code will not produce the output you want. You will reach 1111 in several ways (from 0111, 1011, 1101 and 1110) so your results will not be unique

You can solve this without recursion, simply by converting base-10 integers to base-3:

    for (int i = 0; i < 81; i++) {
        System.out.println(Integer.toString(i, 3));
    }

For more elegant output, use this instead:

    System.out.printf("%04d%n", Integer.parseInt(Integer.toString(i, 3), 10));

If you still want to use recursion, here's a solution:

int numberOfDigits = 4;
int highestDigitValue = 2;

public static void main(String[] args) {
    new Tester().generate("");
}

private void generate(String str) {
    if (str.length() == numberOfDigits) {
        System.out.println(str);
    } else {
        for (int i = 0; i < highestDigitValue + 1; i++) {
            generate(str + i);
        }
    }
}