如何将3个嵌套循环的函数变成一个递归函数？

Question

什么会为下面的函数递归版本会是这样：

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; 
      } 
} 

只是心理钻探。（编辑：强调此行）

Answer 1

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); 
} 

那是递归吗？

Answer 2

我能想到的是将其在被分割到四个功能如下最简单的方法：

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 3

我觉得是这样的：

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 4

这个第一个版本在堆栈空间方面要比在递归调用之间传递所有变量的实践方法更有效率（实际上，你应该能够计算3倍的深度（如果你能弄清楚原因）

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); 
} 

另一种方法，如果你想保持递归调用之间的状态独立性将通过X，Y，&ž单独的通话之间：

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

Answer 5

使用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; 
} 

这不是C++，它甚至不是C，但自从我看到unwind的答案后，它一直困扰着我。

Answer 6

我很想写一个类，只是为了减少参数列表真的。

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(); 
} 

注意，这是使用尾递归 - 如果你幸运的话，你的编译器可能优化成迭代。即使如此，原来的三环版本在几种方式比这更好 - 可读性，效率... ...

我有在实际代码中使用此方法，但不是这样简单的任何事情。