CODEWITHSUNDEEP
javarecursionfor-loopnested-loops
Sophie Sperner
Sophie Sperner

Reputation: 4556

Series of nested loops without recursion

In Java, I have the following general code for integer d equal to 2, 3, 4, ..., dmax - up to a maximum number dmax : d < dmax (so this code is repeated for every value of d in that range):

// d is the number of wrapper loops
int[] ls = new int[d];
...
// let ls array be filled with some arbitrary positive numbers here
...
// first wrapper loop
for (int i1 = 0; i1 < ls[0]; i1++) {

    ...

        // last wrapper loop
        for (int id = 0; id < ls[d - 1]; id++) {

            // internal loop
            for (int j = id + 1; j < ls[d - 1]; j++) {

                myCode();

            }

        }

    ...

}

In case of d = 3 it looks like:

int ls = new int[3];
ls[0] = 5; ls[1] = 7; ls[2] = 5;

for (int i1 = 0; i1 < ls[0]; i1++) {

    for (int i2 = 0; i2 < ls[1]; i2++) {

        for (int i3 = 0; i3 < ls[2]; i3++) {

            for (int j = i3 + 1; j < ls[2]; j++) {

                myCode();

            }

        }

    }

}

I want to gather all that repeated code into a single generalized one. For that purpose I can use the while loop and recursion like below:

int d = 2, dmax = 10;
while (d < dmax) {
    // in algorithm ls is pre-filled, here its length is shown for clearance
    int[] ls = new int[d];
    for (int i = 0; i < ls[0]; i++) {
        doRecursiveLoop(1, d, -1, ls);
    }
    d++;
}

doRecursiveLoop(int c, int d, int index, int[] ls) {

    if (c < d) {
        for (int i = 0; i < ls[c]; i++) {
            // only on the last call we give the correct index, otherwise -1
            if (c == d - 1) index = i;
            doRecursiveLoop(c + 1, d, index, ls);
        }
    } else {
        for (int j = index + 1; j < ls[d - 1]; j++) {

            myCode();

        }
    }

}

Can anybody shed some light as to how I would approach this problem of dynamically occurred nested loops without recursion?

Upvotes: 3

Views: 1185

Answers (1)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272687

You effectively have tail recursion here. Any tail-recursive function can trivially be converted to an iterative function using a loop.

For example:

void foo() {
    // ... Stuff ...

    if (someCondition) {
        foo();
    } else {
        bar();
    }
}

becomes:

void foo() {
    while (someCondition) {
        // ... Stuff ...
    }
    bar();
}

Upvotes: 1

Related Questions