Variable Number of for loops with code in between

Question

So the problem I have is that I want to implement N for loops in the following way (where N is a variable):

for i0=0:MAX
   cOR[0] = initial + move[i0];
       for i1=0:MAX
           cOR[1] = cOR[0] + move[i1];
                ....
                some other stuff inside the final loop

(cOR is a vector of length equal to the number of for loops)

So I found this solution that works when you just have the nested loops (https://stackoverflow.com/a/20577981/3932908) but have been struggling to modify it for my particular case which requires code in between the for loops. Is there a simple way to implement this or is a different approach needed?

What? You can't have the number of actual loops (the number of `for`s in the source code) depend on some run-time value. C is a compiled language, it doesn't work like that. This sounds like an [XY problem](http://xyproblem.info/). — unwind, Sep 28 '16 at 14:16
You can't implement a nested loop with a variable depth. You can have a recursion, if you really want. — Eugene Sh., Sep 28 '16 at 14:17
I agree: this sounds like an XY problem. What is the real problem you're trying to solve? — Jim Mischel, Sep 28 '16 at 14:27
You can easily loop recursively through nested data of unknown size without using the intrinsically horrible language "feature" known as recursive functions. You just need some means to return to the previous level of iteration, is all. — Lundin, Sep 28 '16 at 14:35
OK so I realize that there is no way to implement this directly, but the link I provided shows a solution that gives mimics this but only for the case where there is no code between the nested loops. It just seemed like it should be easy to generalize, but I haven't been able to figure it out yet. — Henry, Sep 28 '16 at 14:41
If you don't want to function call recursion, you can have an array whose length is the number of nested loops, and whose elements contain the terminal count value and a loop counter for the corresponding loop. You also need some code to permute its way though all those loop counters and do something for each permutation. — Ian Abbott, Sep 28 '16 at 14:45
be careful of the language functions properties : it is not the same algo if they transmit the arguments by values — , Sep 28 '16 at 15:29

score 3 · Answer 1 · answered Oct 09 '16 at 12:51

The general approach is to

Write a recursive function.
If recursion is not for some reason appropriate for your code (e.g. very long recursion depth, or the ability to suspend the execution is required), then convert the recursive version to an iterative one by explicitly modeling the stack.

Doing №1 is easy:

void f(int depth, int initial, int *cOR)
{
    if(your termination condition)
    {
        // some other stuff inside the final loop, and...
        return;
    }

    for(int i = 0; i < MAX; ++i)
    {
        cOR[depth] = initial + move[i];
        f(depth+1, cOR[depth]);
    }
}

And call it like so:

f(0, initial, cOR);

Now we head to №2, i.e. converting to a non-recursive version. The extra state we need is what was stored on the stack before: the values of the i variables. So here we go:

int i[max_depth];
int depth = 0;

for(;;)
{
    if(your termination condition)
    {
        // some other stuff inside the final loop, and...

        do {
            if(--depth < 0)
                return;
        } while(++i[depth] >= MAX);
    }
    else
        i[depth] = 0;

    cOR[depth] = (depth > 0 ? cOR[depth-1] : initial) + move[i[depth]];
    ++depth;
}

If you can't estimate max_depth a priori then you can switch to a dynamically allocated array that grows as you need.

Variable Number of for loops with code in between

1 Answers1