java - 嵌套循环的递归

Question

j有没有办法创建以下代码的递归函数？

for(int i=0; i<1000000; i++){
    for(int j=0; j<1000000; j++){
        for(int k=0; k<1000000; k++){
            //Do something using i,j and k
        }
    }
}

我需要它来组合每一个可能的数字序列。例如： (0,0,0) (0,0,1) (0,1,0)

通过这个循环大约需要 10 个小时，所以我必须简化它，我认为递归函数可以做到这一点。

谢谢

Answer 1

理论上，每个迭代循环都可以转换为递归调用（使用无限堆栈或通过tail-call），但是：

1. 递归并不比迭代快——时间复杂度是相同的
2. Java 不支持TCO，因此不支持如此深的递归调用 - 几十个：是的，数百万个：绝对不

在这种情况下，它需要很长时间，因为它循环了很多次。蛮力算法是 O(n ^c )，其中 c 是 3 - 也就是说，边界是多项式时间（这不好），并且 n “相对较大”。这是大量浪费的CPU 周期。

考虑到这么多排列通常不适合直接使用/存储，重新审视原始问题并推导出具有合理时间复杂度的方法可能是有益的。例如，有一种更好的方法来计算排列..

Answer 2

为什么将其转换为递归，这会使它运行得更慢..

但是你可以试试这个：

public static void recursiveLoop (int i, int j, int k, int w, int h, int d)
{

    /* code .. */

    /* increment i,j,k */
    if (k == d)
    {
        k = 0;
        j++;
    }

    if (j == h)
    {
        j = 0;
        i++;
    }

    if (i == w)
    {
        return; // Stop
    }

    recursiveLoop(i,j,k);

}

但是编译器会把它改成这样的：

public static void recursiveLoop (int i, int j, int k, int w, int h, int d)
{

    do
    {

        /* code .. */

        /* increment i,j,k */
        if (k == d)
        {
            k = 0;
            j++;
        }

        if (j == h)
        {
            j = 0;
            i++;
        }

    }while (i != w);

}

Answer 3

考虑下面的递归，详细看这个。 递归比循环快吗？

因此，当您标记 Java 时，递归比迭代更昂贵，因为必须分配堆栈内存。因此，如果您的意图是记录这些排列，那么最好将它们存储到文件中以备后用。这取决于您的问题陈述，可以为此指定更准确的答案。