Recursion의 이해

유용한 두 가지 방법이 있는 것 같다.

1. 귀납적 증명

// Hanoi Tower Problem
void showMoves(int n, char start, char dest, char temp) {
	if (n == 1) {
		printf("Move disk 1 from peg %c to peg %c\n", start, dest);
	}
	else {
		showMoves(n - 1, start, temp, dest);
		printf("Move disk %d from peg %c to peg %c\n", n, start, dest);
		showMoves(n - 1, temp, dest, start);
	}
}

• 함수가 하는 일을 가정한다.
  : showMoves 함수는 n개의 원판을 start에서 temp를 거쳐 dest로 이동시킨다.

• Base Case를 확인한다.
  : 남은 원판이 1개(마지막 원판)가 되면 그 원판을 start에서 dest로 옮긴다.

• 문제를 풀기 위한 Recursive Case를 작성한다.
  : 하노이 타워 문제의 풀이 방법은 다음과 같다.
  : 먼저 위의 (n-1)개 원판을 가운데로 옮긴다.
  : 다음으로 남은 하나의 원반을 오른쪽으로 옮긴다.
  : 가운데의 (n-1)개의 원판을 오른쪽으로 옮긴다.

• 가정했던 함수의 역할을 생각하고 적절히 사용한다.

showMoves (n-1, start, temp, dest);
가정: n-1개의 원판을 start에서 dest를 거쳐 temp로 이동한다.

2. State-Space Tree의 Backtracking

• 현재 매개변수(level 등)의 상태가 Tree의 어느 한 노드에 위치해있다고 가정한다.

• Base Case는 두 가지 경우가 있다.

  • 옳지 않은 길을 갔을 때 Return (Maze 문제에서 !inside인 경우)
  • Leaf 노드에 도착했을 때 Return (Power set 문제에서 탐색할 집합이 공집합이 된 경우)

• Recursive Case에서 다음의 위치에 말을 놓는다.

• 목적에 따라 크게 세 가지 기능이 있다.

  • Decision: True/False를 반환 (길 찾기, nQueen 문제)
  • Counting: integer 반환 (경로 개수 찾기)
  • Optimization: 최적화 문제: 최댓값/최솟값 찾기 (Knapsack 문제)

3. Recursion 따라 들어가기

• 이것은 지양해야하는 Recursion 이해 방법이다.