[Algorithm Week_3] Recursion

Recursion

- 자기 자신을 호출하는 구조?

- 알고리즘 설계 & 문제해결의 필수

 

Recursion의 예

1) Factorial

 

2) 자료구조 (LinkedList & Binary Tree)

LinkedList

• Null은 List이다
• 어떤 A가 List이면, A앞에 노드를 연결한 전체도 List이다

Binary Tree

• 공집합은 Binary Tree이다
• T1, T2가 Binary Tree이면,....

 

---

Reduction? : 줄이기 & 쪼개기

- 알고리즘을 설계할 때 가장 많이 쓰이는 기술 중 하나

 

'Reducing one problem "X" to another problem "Y"'

- 우리가 풀고 싶은 문제는 X이다

- 이 X를 풀 때 Y의 알고리즘을 호출?

- 우리는 Y가 어떤 알고리즘에 의해서 풀리는지는 관심이 없다

- 우리의 관심은 오로지 Y를 활용해서 X를 푸는 것

>> Y를 푸는 알고리즘은 마치 "Black Box"와 같다

- 가려진 "Black Box"에서 Y를 해결하고 그 해결된 어떤 수치를 이용해서 문제 X를 푸는 것이 우리가 지금 원하는 것이다

- "Black Box"에 의해 가려진 Y를 푸는 알고리즘은 우리의 관심사가 아니다

---

Recursion - Reduction

Recursion은 Reduction의 일부라고 볼수도 있다

Why? Reduction은 어떠한 문제 X를 풀 때 Y라는 해결된 문제를 이용하는 것이고, 여기서 "X == Y"라는 조건이 성립하면 그것이 바로 Recursion이다

Recursion은 같은 문제를 Reduction하는 기법으로, 동일한 문제에 대해 "Input Size"가 줄어드는(reduce)방식이다

int fact(int n){
    if(n == 1) return 1;
    else return n*fact(n-1);
}

- 대표적 재귀 알고리즘인 Factorial을 보면 fact를 재귀적으로 호출하는데 "Input Size"는 줄어드는 것을 볼 수 있다

 

---

Hanoi Tower

- 대표적 재귀문제 중 하나인 "하노이 탑"

우리는 3개의 tower가 존재하고, N개의 원판을 3번째 tower로 전부 옮기고 싶다

But, 여기에는 조건들이 존재한다

1. 큰 원판은 절대로 작은 원판 위에 존재하면 안된다
2. 한번에 하나의 원판만 옮길 수 있다

여기서 문제를 넓게 바라보면, 결국 N개의 원판 중 (N-1)개의 원판을 second tower로 옮기고 가장 밑에 있는 가장 큰 원판을 third tower로 옮겨버리고, 이 다음에 second tower로 옮긴 (N-1)개의 원판을 최종적으로 third tower로 옮기면 문제가 해결된다

>> 여기서 (N-1)개의 원판을 move하는 과정은 '재귀에게 던져버리면 된다'

static void Hanoi_Recursion(int n, char src, char tmp, char dst){
    /*
    n개의 원판 옮기기
    src에서 dst로 :: 중간에 tmp를 거쳐서
     */
    if(n > 0) {
        Hanoi_Recursion(n - 1, src, dst, tmp);
        /*
        일단 위의 (n-1)개의 원판을 tmp로 옮겨버리기
        -> tmp를 중간 거쳐가는 지점으로 활용
         */
        System.out.printf("원판 %d : %c -> %c\n", n, src, dst);
        /*
        맨 밑의 원판은 src에서 dst로 도착
        ## 원판들의 실제 move (recursion 내에서의 move)는 여기서 발생
         */
        Hanoi_Recursion(n - 1, tmp, src, dst);
        /*
        처음에 tmp로 옮겨진 (n-1)개의 원판을 최종 목적지인 dst로 옮기기
        -> 여기서 src를 중간 거쳐가는 지점으로 사용
         */
    }
}

- 결국 (N-1)개의 원판을 옮기는 것은 우리가 최종적으로 원하는 문제인 "N개의 원판을 옮기기"를 reduction해서 해결하는 과정이다

 

Hanoi Tower - Time Complexity

Hanoi(n, src, dst, tmp)을 실행했을 때의 연산 수행 횟수 함수를 T(n)이라고 정의하면

- move하는 과정은 "상수"만큼의 시간이 걸리고

- 재귀과정은 T(n-1)의 시간이 걸릴 것이다

## n = 0 ##
T(n) = 0

## n > 0 ##
T(n) = 2*T(n-1) + 1

 

---

MergeSort & QuickSort

Recursion을 사용하는 대표적인 정렬 알고리즘들이다

[Algorithm Week_3] MergeSort

 

[Algorithm Week_3] QuickSort