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

注意，這是使用尾遞歸 - 如果你幸運的話，你的編譯器可能優化成迭代。即使如此，原來的三環版本在幾種方式比這更好 - 可讀性，效率... ...

我有在實際代碼中使用此方法，但不是這樣簡單的任何事情。