Recursion

Recursion을 사용한 연산

하노이탑

규칙

1. 한번에 한 디스크만 움직일 수 있음
2. 가장 위에 있는 디스크만 움직일 수 있음
3. 더 큰 디스크가 작은 디스크 위에 위치할 수 없음
4. 중간 기둥은 보조역할로 사용될 수 있음

• 해당 문제를 n개의 원반의 개수를 가질 때 풀 수 있도록 일반화

  매개변수 :
  원반 n, 시작 지점 from, 중간 지점 temp, 목표 지점 to
  (n은 몇번째 원반인지를 나타냄)

  1. n이 1과 같으면 가장 밑에 있는 원반이므로 to 지점으로 이동
     2-1. 그렇지 않은 경우 모든 원반을 temp으로 이동
     2-2. 하나 남은 원반을 to로 이동
     2-3. temp의 원반들을 to로 이동

코드로 구현

void hanoiTower(int n, char from, char temp, char to)
{
	if(n == 1) 
    	//1번 원반을 from에서 to로 이동
    else
    {
    	hanoiTower(n-1, from, to, temp)
        //n번 원반을 from에서 to로 이동
        hanoiTower(n-1, tmp, from, to)
    }
   	
}

n = 4일 때의 예시 (from = A, tmp = B, to = C)

1. hanoiTower(3, A, C, B) 호출
   1-1-1. hanoiTower(2, A, B, C) 호출
   1-1-2. hanoiTower(1, A, C, B) 호출
   n이 1이므로 1번 원반을 A에서 B로 이동 후 hanoiTower(2, A, B, C)로 돌아감

   1-1-3. hanoiTower(2, A, B, C)에서 2번 원반을 A에서 C로 이동
   1-1-4. hanoiTower(1, B, A, C) 호출
   n이 1이므로 1번 원반을 B에서 C로 이동 후 hanoiTower(2, A, B, C)로 돌아간 후 함수가 종료되었으므로 hanoiTower(3, A, C, B)로 돌아감

   1-2-1. 3번 원반을 A에서 B로 이동

   1-3-1. hanoiTower(2, C, A, B) 호출
   1-3-2. hanoiTower(1, C, B, A) 호출
   n이 1이므로 1번 원반을 C에서 A로 이동 후 hanoiTower(2, C, A, B)로 돌아감
   1-3-3. hanoiTower(2, C, A, B)에서 2번 원반을 C에서 B로 이동
   1-3-4. hanoiTower(1, A, C, B) 호출
   n이 1이므로 1번 원반을 A에서 B로 이동 후 hanoiTower(2, C, A, B)로 돌아감 돌아간 후 함수가 종료되었으므로 hanoiTower(3, A, C, B)로 돌아감

2. 4번 원반을 A에서 C로 이동

3. hanoiTower(3, B, A, C) 호출
   3-1-1. hanoiTower(2, B, C, A) 호출
   3-1-2. hanoiTower(1, B, A, C) 호출
   n이 1이므로 1번 원반을 B에서 C로 이동 후 hanoiTower(2, B, C, A)로 돌아감
   3-1-3. hanoiTower(2, B, C, A)에서 2번 원반을 B에서 A로 이동
   3-1-4. hanoiTower(1, C, B, A) 호출
   n이 1이므로 1번 원반을 C에서 A로 이동 후 hanoiTower(2, B, C, A)로 돌아감 돌아간 후 함수가 종료되었으므로 hanoiTower(3, B, A, C)로 돌아감

   3-2-1. 3번 원반을 B에서 C로 이동

   3-3-1. hanoiTower(2, A, B, C) 호출
   3-3-2. hanoiTower(1, A, C, B) 호출
   n이 1이므로 1번 원반을 A에서 B로 이동 후 hanoiTower(2, A, B, C)로 돌아감
   3-3-3. hanoiTower(2, A, B, C)에서 2번 원반을 A에서 C로 이동
   3-3-4. hanoiTower(1, B, A, C) 호출
   n이 1이므로 1번 원반을 B에서 C로 이동 후 hanoiTower(2, A, B, C)로 돌아감 돌아간 후 함수가 종료되었으므로 hanoiTower(3, B, A, C)로 돌아감

4. 모든 과정이 종료되었으므로 hanoiTower(4, A, B, C) 함수를 종료

Recursion 연산의 종류

Linear Recursion(선형 재귀)

• 단일한 재귀 연산만 발생
  Ex) 팩토리얼 연산, x^n(power) 연산

Binary Recursion(이진 재귀)

• 2개의 재귀 연산이 발생
  Ex) 피보나치 연산, 하노이 탑 연산

Multiple Recursion(다중 재귀)

• 2개 이상의 재귀 연산이 발생
• 이진 재귀 연산도 이에 포함됨
  Ex) Blob Coloring, Maze Traversal

Blob Coloring

• 서로 연결되어있지 않은 영역을 다른 색으로 색칠하는 것
• 이미지를 픽셀 단위로 스캔하다가 색 값을 가진 픽셀을 만나면 해당 픽셀의 이웃 4개 픽셀을 재귀 탐색
• 같은 색을 가진 연결된 영역들을 라벨링할 수 있음

Maze Traversal

• 깊이 우선 탐색으로 주변 4개 방향의 경로가 접근가능한지 탐색
• 4방향에 대한 다중 재귀 탐색으로 경로를 찾을 수 있음