How do I turn a function from 3 nested loops into one recursive function?
What would be the recursive version for the following function:
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;
}
}
For mental drilling only. (Edit: this line is underlined)
source to share
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);
}
source to share
The easiest way I can think of is to split it into four functions like this:
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);
}
}
source to share
This first version is much more efficient in terms of stack space than the naiive approach of passing all variables between recursive calls (in fact, you should be able to compute 3 times as much (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 recursive calls, would be to pass x, y, and z separately between calls:
tri_loop(x, y, z + 1, l);
source to share
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 correct C, but it has bothered me ever since I saw you reverse the answer.
source to share
I would be tempted to write a class just to actually shorten the parameter lists.
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 can optimize it in iteration. However, the original version of the three loops is better in several variations than this - readability, efficiency, ...
I've used this method in real code, but not for something so simple.
source to share