루프를 사용하여 재귀 적으로 재귀 코드

Question

안녕하세요,이 코드를 비 재귀 적으로 사용하려면 어떻게해야합니까?

public class test { 

    public static void main(String[] args) { 
     int[] array = new int[]{0, 1, 2,3}; 
     int size = 2; 
     int[] tmp = new int[size]; 
     //Arrays.fill(tmp, -1); 
     generateCombinations(array, 0, 0, tmp); 
    } 

    private static void generateCombinations(int[] array, int start, int depth, int[] tmp) { 

     if (depth == tmp.length) { 
      for (int j = 0; j < depth; j++) { 
       System.out.print(array[tmp[j]]); 

      } System.out.println(); 
      return; 
     } 
     for (int i = start; i < array.length; i++) { 
      tmp[depth] = i; 
      generateCombinations(array, i + 1, depth + 1, tmp); 
     } 

    } 
} 

특정 조합으로 모든 조합을 생성합니다.

Answer 1

모든 반복은 반복으로, 그 반대로는 다시 작성 될 수 있습니다. 당신은 일반적인 알고리즘을 수행 할 필요가 :

• Replace Recursion with Iteration
• Replace Iteration with Recursion

1. 는 재귀의 기본 케이스를 결정합니다. Base case에 도달하면 재귀가 종료됩니다. 모든 재귀에는 정의 된 기본 대소 문자가 있어야합니다. 또한 각 재귀 호출은 기본 사례 인 을 향해 진행해야합니다 (그렇지 않은 경우 재귀 호출은 무한으로 번 수행됩니다). 이 예제에서 기본 경우는 n == 0입니다.
2. 기본 대소 문자에 도달 할 때까지 반복되는 루프를 구현하십시오.
3. 기본 케이스쪽으로 진행하십시오. 새 인수를 반복 메서드 대신 루프 맨 위로 보냅니다.

뒤에는 불변 조건을 유지하는 개념이 있습니다.

Answer 2

이 시도 :

public class Test { 
    private final int[] array; 
    private final int[] tmp; 

    private Test(int[] array, int size) { 
     tmp = new int[size]; 
     this.array = array; 
    } 

    public static void main(String[] args) { 
     Test t = new Test(new int[] {0, 1, 2, 3}, 2); 
     t.generateCombinations(); 
    } 

    /** 
    * Print the selection. 
    */ 
    private void print() { 
     for (int i : tmp) { 
      System.out.print(array[i]); 
     } 
     System.out.println(); 
    } 

    /** 
    * Set values in tmp for indices startIndex, ..., (tmp.length-1) 
    * to startValue, ..., (startValue-startIndex + tmp.length-1) 
    * @param startIndex 
    * @param startValue 
    */ 
    private void initMin(int startIndex, int startValue) { 
     final int offset = startValue - startIndex; 
     for (int i = startIndex; i < tmp.length; i++) { 
      tmp[i] = i+offset; 
     } 
    } 

    private void generateCombinations() { 
     if (tmp.length == 0) return; 
     initMin(0, 0); 
     print(); 

     final int maxIndex = tmp.length-1; 
     int index = maxIndex; 
     final int z = array.length-tmp.length; 

     while (index >= 0) { 
      if (tmp[index] == index+z) { 
       index--; 
      } else { 
       if (tmp[index]== index+z-1) { 
        // only value at index changes 
        tmp[index]++; 
        index--; 
       } else { 
        initMin(index, tmp[index]+1); 
        index = maxIndex; 
       } 

       print(); 
      } 
     } 
    } 
} 

를 알고리즘은 다음과 같은 관찰을 기반으로합니다 tmp[i]이 최대 (i+array.length-tmp.length)

알고리즘은 항상 항상이 여전히 가능하다 마지막 위치에서 1을 추가해야합니다 다음 위치의 값을 가능한 한 작은 값으로 설정합니다.