How to turn a function of 3 nested loops into one recursive function?

Question

what would the recursive version for the following function would be like:

void tri_loop(size_t i, size_t j, size_t k)
{
    for(size_t x = 0; x < i; ++x)
        for(size_t y = 0; y < j; ++y)
            for(size_t z = 0; z < k; ++z)
            {
                cout << x <<y << z;
            }
}

Just for mental drilling.(Edit: emphasized this line)

Answer 1

The easiest way I can think of would be to be split it in to four functions as follows:

void tri_loop(size_t j, size_t k, size_t K) {
    tri_loopX(0,i,j,k);
}

void tri_loopX(size_t x, size_t i, size_t j, size_t k) {
    if (x >= i) {
        return;
    } else {
        tri_loopY(x, 0, j, k);
        tri_loopX(++x, i, j, k);
    }
}

void tri_loopY(size_t x, size_t y, size_t j, size_t k) {
    if (y >= j) {
        return;
    } else {
         tri_loopZ(x, y, 0, k);
         tri_loopY(x, ++y, j, k); 
    }
}

void tri_loopZ(size_t x, size_t y, size_t z, size_t k) {
    if (z >= k) {
        return;
    } else {
        cout << x << y << z;
        tri_loopZ(x, y, ++z, k);
    }
}

Answer 2

I think something like this:

void tri_loop_work(size_t i, size_t imax, size_t j, size_t jmax, size_t k, size_t kmax)
{
  std::cout << "i=" << i << ", j=" << j << ", k=" << k << std::endl;
  if(k < kmax)
    tri_loop_work(i, imax, j, jmax, k + 1, kmax);
  else if(j < jmax)
    tri_loop_work(i, imax, j + 1, jmax, 0, kmax);
  else if(i < imax)
    tri_loop_work(i + 1, imax, 0, jmax, 0, kmax);
}

void tri_loop(size_t imax, size_t jmax, size_t kmax)
{
  tri_loop_work(0, imax, 0, jmax, 0, kmax);
}

Answer 3

This first version is much more efficient in terms of stack space than a naiive approach passing all the variables between the recursive calls (in fact, you should be able to calculate 3 times as deep (if you can figure out why).

struct State {
    size_t x, y, z;
};

struct Limits {
    size_t i, j, k;
};

void tri_loop(struct State *s, const struct Limits *l)
{
    if (s->z == l->k) {
        s->y++;
        s->z = 0;
    }
    if (s->y == l->j) {
        s->x++;
        s->y == 0;
    }
    if (s->x == l->i + 1)
        return;

    cout << s->x << s->y << s->z;
    s->z++;
    tri_loop(s, l);
}

Another approach, if you want to maintain state independence between the recursive calls would be to pass x, y, & z individually between the calls:

tri_loop(x, y, z + 1, l);

Answer 4

Using GCC:

#include <stdio.h>

void tri_loop(size_t ii, size_t jj, size_t kk)
{
  void tri_loop_inner(size_t i, size_t j, size_t k)
  {
    printf("i=%d j=%d k=%d \n", i, j, k);

    if(k < kk)
        tri_loop_inner(i,j,k+1);
    else if(j < jj)
        tri_loop_inner(i,j+1,0);
    else if(i < ii)
        tri_loop_inner(i+1,0,0);
  }

  tri_loop_inner(0, 0, 0);
}

int main()
{

        tri_loop(3,3,3);
        return 0;
}

It's not C++, and it's not even proper C, but it's been bothering me ever since I saw unwind's answer.

Answer 5

void recurse(accumulator,b,c,d,limit)
{
  if (limit == 0)
    printf("%i %i %i\n", b, c, d);
  else
    if (accumulator<limit)
    {
      recurse(accumulator+1,b,c,d,limit);
      recurse(0,accumulator,b,c,d);
    }
}

main()
{
  int x=2,y=3,z=4;
  recurse(0,0,x,y,z);
}

Is that recursive enough?

Answer 6

I'd be tempted to write a class, just to cut down on the parameter lists really.

class tri_loop_tool
{
  private:
    size_t x, y, z;
    size_t i, j, k;

    void Over_z ();
    void Over_y ();
    void Over_x ();

  public:
    void operator() (size_t pi, pj, pk);
};

void tri_loop_tool::Over_z ()
{
  if (z < k)
  {
    cout << x << ", " << y << ", " << z << endl;
    z++;    Over_z ();
  }
}

void tri_loop_tool::Over_y ()
{
  if (y < j)
  {
    z = 0;  Over_z ();
    y++;    Over_y ();
  }
}

void tri_loop_tool::Over_x ()
{
  if (x < i)
  {
    y = 0;  Over_y ();
    x++;    Over_x ();
  }
}

void tri_loop_tool::operator() (size_t pi, pj, pk)
{
  i = pi; j = pj; k = pk;
  x = 0;  Over_x ();
}

Note that this is using tail recursion - if you're lucky, your compiler might optimise it into iteration. Even so, the original three loops version is better in several ways than this - readability, efficiency, ...

I have used this method in real code, but not for anything this simple.