기본 케이스가없는 재귀가 어떻게 나옵니 까

Question

그래서 txt 파일에서 얻는 미로를 재귀 적으로 풀어내는이 프로그램에서 일하고 있습니다. 나는 미로를 2 차원 배열에 넣었다. 다음은 가장 간단한 미로의 예입니다.

+-+-+-+ 
|S| | 
+ + + + 
| |E| 
+-+-+-+ 

내가 메신저 아마 가장 좋은 방법으로 미로를 해결하지 않을 알고하지만 난 내 방식대로 난 그냥 내 재귀 루프의 탈옥하는 방법을 알 필요가 작동합니다 생각합니다. 내가하고있는 일은 다음 장소에 하숙인이 있는지 확인하는 것입니다. 그 다음에 '*'가 두 개있는 경우 나중에 그곳으로 이동하여 마커를 내려 놓습니다. 이것은 나를 미로의 끝으로 데려 갔다. 그러나 그것은 부서진다. 루프를 벗어나는 방법이 필요합니다. 방금 재귀에 대해 배우기 시작 했으므로 문제는 아니지만 정확히 확신하지는 않습니다.

잘못된 선택 방법은 열린 경계선이있는 셀과 두 자리에 '*'가없는 셀이있는 마지막 위치로 나를 반환합니다.

public static void solveMaze(int COL, int ROW){ 
    //find first open cell and choose it 

     if(drawArray[COL][ROW+1] == ' ' && drawArray[COL][ROW+2] != '*'){ 
      //if(drawArray[COL][ROW+2] == 'E') 

      drawArray[COL][ROW+2] = '*'; 
      ROW+= 2; 
      solveMaze(COL,ROW); 
     } 
     else if(drawArray[COL+1][ROW] == ' ' && drawArray[COL+2][ROW] != '*'){ 
      drawArray[COL+2][ROW] = '*'; 
      COL+= 2; 
      solveMaze(COL,ROW); 
     } 
     else if(drawArray[COL][ROW-1] == ' ' && drawArray[COL][ROW-2] != '*'){ 
      drawArray[COL][ROW-2] = '*'; 
      ROW-= 2; 
      solveMaze(COL,ROW);   
     } 
     else if(drawArray[COL-1][ROW] == ' ' && drawArray[COL-2][ROW] != '*'){ 
      drawArray[COL-2][ROW] = '*'; 
      COL+= 2; 
      solveMaze(COL,ROW); 
     } 
     else 
      wrongChoice(COL,ROW); 


    } 

Answer 1

하나는 파라미터로서 부분 결과 (처음에 비어)을 제공 할 수있다. 그리고 하나는 결과를 반환 할 수 있습니다. 재귀를위한 또 다른 매개 변수는 종종 가능한 후보 집합입니다. 같은 인스턴스 뭔가

:

public static void solveMaze(int COL, int ROW, Path pathTaken) { 
    Path pathTaken = new Path(); 
    if (solveMazeRecursively(START_COL, START_ROW, pathTaken)) { 
     ... 
    } 
} 

private static boolean solveMazeRecursively(int COL, int ROW, Path pathTaken) { 
    if (drawArray[COL][ROW+1] == 'E') { 
     System.out.println(pathTaken); 
     return true; 
    } 
    // The real work... 
    if (drawArray[COL][ROW+1] == ' ' && drawArray[COL][ROW+2] != '*'){ 
     drawArray[COL][ROW+2] = '*'; 
     ROW += 2; 
     takenPath.add(COL, ROW+2); 
     if (solveMazeRecursively(COL,ROW, takenPath)) { 
      return true; 
     } 
     takenPath.remove(COL, ROW+2); 
    } 

재귀 의미 게으른 아무것도 (솔루션 존재가 불가능하거나 계속하기 위해) 할 수 없습니다 여부를 먼저 확인하고, 그렇지 않으면 새로운 기능 인스턴스에 위임.