Recursion for nested loops

Question

jIs there a way to create a recursive function of the following code?

for(int i=0; i<1000000; i++){
    for(int j=0; j<1000000; j++){
        for(int k=0; k<1000000; k++){
            //Do something using i,j and k
        }
    }
}

I need it to combine every possible sequence of numbers. eg: (0,0,0) (0,0,1) (0,1,0)

It took about 10 hours to pass through this loops, so i have to simplify it and i think a recursive function could do it.

Thanks

Is there a way? Sure. Do I see a reason to? No. Could you elaborate as to why recursion would be better than iteration in this case? — Makoto, Mar 26 '13 at 04:35
If I am not wrong, everything that can be done using iteration can be done using recursion, you just need to think of a way to achieve it. — Abubakkar, Mar 26 '13 at 04:35
Also, you use 'i' in the termination of the 'j' for loop. Just saying. — pandorym, Mar 26 '13 at 04:36
@Abu In theory: yes. In practice: it depends. Java does not support TCO, so recursion has a finite depth in Java. — , Mar 26 '13 at 04:49
recursion does no improvement in the performance. its just a 'cleaner' way of writing repetitive/looping instruction. — Ankit, Mar 26 '13 at 04:52
I think parallel processing would be a better idea. If you have 8 cores, you can (in a perfect world) drop the execution time to 10/8 = 1.25 hours. — Bernhard Barker, Mar 26 '13 at 09:03
Welcome to Stack Overflow! StackOverflow is not the proper place for this question. We do not write your code for you. You need to do your own coding and if you aren't sure why something is not working as expected, post the code with an explanation of what you were expecting it to do, and what it is actually doing including all error messages. See [about StackOverflow](http://stackoverflow.com/about). — Lightness Races in Orbit, Mar 26 '13 at 09:48

score 3 · Answer 1 · 2013-03-26T17:22:36.277

3

In theory, every iterative loop can be converted to a recursive call (with either an infinite stack or via a tail-call), however:

Recursion is not faster than iteration - the time complexity is identical
Java does not support TCO and thus does not support such deep recursive calls - tens of dozens: yes, millions: absolutely not

In this case it takes a long time because it loops a ridiculous number of times. The brute force algorithm is O(n^c), where c is 3 - that is, the bounds are polynomial time (this is not good) and n is "relatively large". That's a lot of wasted CPU cycles.

Considering that this many permutations is generally not sane to use/store directly anyway, it might be beneficial to revisit the original problem and derive an approach with a reasonable time complexity. For instance, there is a much better way to count permutations ..

edited Mar 26 '13 at 17:22

answered Mar 26 '13 at 05:01

@Dukeling 1. [Constants are factored out](http://en.wikipedia.org/wiki/Big_O_notation) ("wall-clock" time may differ for a particular n) 2. Sure, it's possible to recurse in only one dimension. – Mar 26 '13 at 09:07
Oh right, complexity. Updated comment - 1) The time complexity may be identical, but, in Java, recursion is generally slower ([this](http://stackoverflow.com/a/2651200/1711796) briefly mentions it), although only by a smallish constant factor, but, given the simplicity of the given code, it could make a greatly significant difference. 2) The way I'm thinking of only requires a recursion depth of 3, not millions. Not sure how else you'd want to do it. – Bernhard Barker Mar 26 '13 at 09:12

Khaled.K · Answer 2 · 2013-03-26T16:14:49.410

1

Why convert that to recursive, that's gonna make it run slower ..

But you can try this:

public static void recursiveLoop (int i, int j, int k, int w, int h, int d)
{

    /* code .. */

    /* increment i,j,k */
    if (k == d)
    {
        k = 0;
        j++;
    }

    if (j == h)
    {
        j = 0;
        i++;
    }

    if (i == w)
    {
        return; // Stop
    }

    recursiveLoop(i,j,k);

}

But the compiler will change it into something like this:

public static void recursiveLoop (int i, int j, int k, int w, int h, int d)
{

    do
    {

        /* code .. */

        /* increment i,j,k */
        if (k == d)
        {
            k = 0;
            j++;
        }

        if (j == h)
        {
            j = 0;
            i++;
        }

    }while (i != w);

}

edited Mar 26 '13 at 16:14

answered Mar 26 '13 at 05:55

Khaled.K

5,828
1
33
51

2

`"the compiler will change it into this"` - I strongly doubt that. They may functionally be the same, but the compiler will not convert a recursive function into iterative (at least it won't in Java). – Bernhard Barker Mar 26 '13 at 08:51
@Dukeling You're right, I'm not sure about most of them, but I know that converting tail-recursion into a while-loop is a common compiler syntax-optimization, what is highly unlikely is the modulo tail-recursion optimization – Khaled.K Mar 26 '13 at 12:40
2

Note that Java / the JVM doesn't support tail call optimization. [Related](http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations). Also note that because the check is at the end, it will probably be `do { ... } while ();`, not `while () { ... }`. – Bernhard Barker Mar 26 '13 at 14:56

score 0 · Answer 3 · edited May 23 '17 at 12:30

Consider the following thing Recursion , go through this for detail . Is recursion ever faster than looping?

So as you tagged Java , recursion is more expensive over iteration as stack memory has to to allocated . So, if your intention is to record those permutation , then better you store them to file for later use . And it depends on your problem statement one can specify more accurate answer for this .

Recursion for nested loops

3 Answers3