Рекурсия для вложенных циклов

Question

jI Есть ли способ создать рекурсивную функцию следующего кода?

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, то есть the bounds are polynomial time (это не хорошо), а n является «относительно большим». Это многоwasted CPU cycles.

Учитывая, что это много перестановок обычно не вменяемый использовать/магазин непосредственно в любом случае, это может быть полезно для вернуться к исходной задаче и получить подход с разумной временной сложностью. Например, есть намного лучший способ подсчета перестановок.

Answer 2

Рассмотрите следующее, рекурсия, пройдите это подробно. Is recursion ever faster than looping?

Так как вы отметили Java, рекурсия стоит дороже итерации, поскольку память стека должна выделяться. Итак, если вы намерены записать эту перестановку, тогда лучше сохранить их в файл для последующего использования. И это зависит от вашего заявления о проблеме, для которого можно указать более точный ответ.

Answer 3

Почему преобразования, что рекурсивный, что собирается сделать его работать медленнее ..

Но вы можете попробовать это:

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

}