순환 (Recursion)

• 모든 순환함수는 반복문(iteration)으로 변경 가능하다.
• 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능하다.
• 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
• 하지만 함수 호출에 따른 오버헤드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등)
• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.
• 모든 case는 결국 base case로 수렴해야 한다.

 

연습

 

미로찾기

미로

 

입구는 (0,0)이고 출구는 (n-1, n-1)일때 입구에서 출구까지 도착하는 경우의 수를 찾아보자

 

현재 위치에서 출구까지 가는 경로가 있으려면

1. 현재 위치가 출구이거나 혹은
2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경우가 있거나

둘 중 하나이다.

 

우선 답이 yes 인지 no 인지 경로가 있는지 없는지 생각해보자

boolean findPath(x, y) { // 현재 좌표의 x,y 를 파라미터로 넘긴다.
	if (x, y) is the exit { // 현재 위치가 출구라면 true를 리턴한다.
    	return true;
    } else {
    	for each neighbouring cell(x', y') of (x, y) do { // (x', y') 이웃한 이웃셀 최대 4개
        	if (x', y') is on the pathway { // 벽이 아니라면
            	if findPath(x', y') {
                	return true;
                }
            }
        }
        return false;	
    }
}

 

간략하게 생각해보면 위와 같이 생각해볼 수 있다. 위에 코드가 무한루프에 빠지는지 반드시 확인해봐야 한다. 

이건 무한루프에 빠질 수 있다. (x',y') 입장에서 (x, y)는 다시 인접한 셀이된다. 그래서 무한하게 양쪽 셀을 반복하는 경우가 발생할 수 있다.

 

그렇기 때문에 내가 방문했던 적이 있는 셀인지 아닌지 확인하는 코드가 더 들어가야 한다.

 

boolean findPath(x, y) { // 현재 좌표의 x,y 를 파라미터로 넘긴다.
	if (x, y) is the exit { // 현재 위치가 출구라면 true를 리턴한다.
    	return true;
    } else {
    	mark (x, y) as a visited cell; // 방문했다고 표시한다.
    	for each neighbouring cell(x', y') of (x, y) do { // (x', y') 이웃한 이웃셀 최대 4개
        	if (x', y') is on the pathway and not visited { // 벽이 아니고 방문한 적이 없는 경우
            	if findPath(x', y') {
                	return true;
                }
            }
        }
        return false;	
    }
}

 

 

자바코드로 풀이해보자

입력값

 

public static boolean findMazePath(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= N) { // x,y가 범위를 벗어나는 경우
    	return false;
    } else if (maze[x][y] != PATHWAY_COLOUR) { // 길이 아닌 경우
    	return false;
    } else if (x == N-1 && y == N-1) { // 도착지점에 도착한 경우
    	maze[x][y] = PATH_COLOUR;
        return true;
    } else { 
    	maze[x][y] = PATH_COLOUR; // 방문한 곳으로 변경한다.
        if (findMazePath(x-1, y) || findMazePath(x, y+1) 
        	|| findMazePath(x+1, y) || findMazePath(x, y-1)) {
            	return true;
            }
            maze[x][y] = BLOCKED_COLOUR; 
            return false;
    }
}