Recursion

EBAB!·2023년 9월 15일

Algorithm & DA

목록 보기

6/12

1. 재귀(Recursion)

어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 가지고 있다고 얘기합니다. 흔히 프로그래밍에서는 함수 내부에서 자신을 다시 호출하는 기능을 제공하는데 이를 재귀(recursion)라고 합니다.

재귀는 컴퓨터 과학 이론의 근간을 이루는 아주 중요한 개념입니다. 재귀 개념은 대표적으로 정렬(Sorting), Heap, Tree, Graph에서 사용되고 잘 활용하면 깔끔하게 코드를 작성할 수 있기 때문에 제대로 재귀적으로 생각하는 방법을 익히는 것이 중요합니다.

2. 수학적 귀납법과 재귀

2-1. 수학적 귀납법 (Mathematical Induction)

수학적 귀납법은 수학에서 명제가 모든 자연수에 대해 참임을 증명하는 방법 중 하나입니다. 기본 아이디어는
“자신보다 작은 명제가 참이라고 증명하고, 자신도 따라서 참이라는 것을 보이는” 방식입니다.

수학적 귀납법을 사용해서 명제를 증명하는 방법은 다음과 같습니다.

**기본 단계(Base Case)**

먼저, 가장 작은 자연수(보통 1 또는 0)에 대해 명제가 참인지 확인합니다.
**귀납 단계(Inductive Step)**

“어떤 자연수 $k$ 에 대해 명제가 참이면, $k+1$ 에 대해서도 참일 것이다"라고 가정(inductive hypothesis)하고 증명합니다.

이 두 단계를 모두 증명하면, 명제는 모든 자연수에 대해 참이라고 할 수 있습니다.

2-2. 재귀

수학적 귀납법과 재귀는 비슷한 논리적 구조와 접근 방식을 사용하고 있습니다.

둘 다 “자신보다 작은 명제가 참이라고 증명하고, 자신도 따라서 참이라는 것을 보이는” 전략을 채택하고 있으며, “기본 경우(base case)의 중요성”을 공유하고 있습니다. 다만 차이점은 수학적 귀납법은 '증명'에 초점을 맞춘 것이고, 재귀는 '문제 해결'에 초점을 맞추고 있습니다.

모든 재귀 알고리즘은 명시적 혹은 암묵적으로 다음 구성요소를 반드시 갖추어야 합니다.

경계 조건(Base Case)

재귀 알고리즘은 종료 조건이 필요합니다. 이를 기본 경우(base case)라고 부르며, 이 경우에는 알고리즘이 더 이상 재귀 호출을 하지 않고 바로 결과를 반환합니다.
재귀 호출(Recursive Case)

자신( $recursion(k+1)$ ) 보다 작은 문제( $recursion(k)$ )에 대해서 이 알고리즘(명제)가 작동한다면, 자신에 대해서 작동한다.

3. 재귀적 구조를 작고 있는 알고리즘들

3-1. 등차 수열

"2, 4, 6, 8, ... 이렇게 더해 나가는 수열이 있을 때, n 번째 항까지의 합을 구하는 함수를 만들어보세요.”라는 문제가 주어졌을 때, 이 등차수열의 문제를 처음 본다고 가정하고, 귀납적으로 접근하는 예시입니다.

1단계 : 문제 파악

해결하려고 하는 문제는 등차수열 2, 4, 6, 8, ... 에서 n 번째 항까지의 합을 구하는 것

2단계 : 기본 단계 (Base Case)

기본 단계는 가장 간단한 경우입니다. 여기서는 첫 번째 항까지의 합을 구하는 것이죠. 그것은 첫 번째 항이 2이므로 답은 2입니다.

3단계 : 귀납 단계 (Inductive Step)

이제 두 번째 항까지의 합을 구해 봅시다. 첫 번째 항까지의 합(2)에 두 번째 항(4)을 더하면 됩니다. 즉, 2+4=6이 됩니다. 세 번째 항까지의 합을 구하려면 어떻게 해야 할까요? 두 번째 항까지의 합(6)에 세 번째 항(6)을 더하면 됩니다. 즉, 6+6=12입니다.

4단계 : 귀납 단계 (Inductive Step)

n번째 항까지의 합을 구하려면 n−1번째 항까지의 합에 n 번째 항을 더하면 됩니다. 이것이 귀납적 규칙이 됩니다.

5단계 : 귀납 단계 (Inductive Step)

자신(”n 번째 항 까지의 합을 구하라!”) 보다 작은 문제(”n - 1 번째 항 까지의 합을 구하라!”)에 대해서 이 알고리즘(명제)가 작동한다면, 자신에 대해서 작동합니다.

```python
def sum(n):
    # 경계 조건(Base Case)
    if n == 1:
        return 2

    # 재귀 호출(Recursive Case)
    else:
        an = 2 + (n - 1) * 2
        return sum(n - 1) + an
```

6단계 : 귀납 단계 (Inductive Step)

n을 5라고 한다면,

호출 순서

    sum(5) = sum(4) + a_5                                      (1) sum(5) 호출
    ------------------------------------------------------------------------
    		     sum(4) = sum(3) + a_4                             (2) sum(4) 호출
    ------------------------------------------------------------------------
    				  		    sum(3) = sum(2) + a_3                    (3) sum(3) 호출
    ------------------------------------------------------------------------
    				  		             sum(2) = sum(1) + a_2           (4) sum(2) 호출
    ------------------------------------------------------------------------
    				  		                      sum(1) = 2             (5) sum(1) 호출

3-2. 하노이 탑

세 개의 기둥 A, B, C가 있습니다. 기둥 A에는 n개의 원판이 작은 것이 위에 오도록 차례대로 쌓여 있습니다. 목표는 기둥 A에 있는 모든 원판을 기둥 B로 옮기는 것입니다. 단, 다음의 규칙을 지켜야 합니다.

한 번에 하나의 원판만 옮길 수 있습니다.
더 큰 원판이 더 작은 원판 위에 있어서는 안 됩니다.
기둥 A 이외의 기둥 (B 또는 C)도 임시적으로 원판을 저장할 수 있습니다.

귀납방법

$n$ 개의 원판이 있다고 가정하면, 가장 큰 원판을 제외하고 $n−1$ 개의 원판을 임시 기둥인 중간 지점(C)로 옮깁니다.
가장 큰 원판을 목표점(B)로 옮깁니다.
중간 지점(C)에 있는 $n−1$ 개의 원판을 목표점(B)로 옮깁니다.

알고리즘

def move(n, source, target, auxiliary):
	if n == 1:
    	print(f"Move disk 1 from {source} to {target}")
        return
    move(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    move(n - 1, auxiliary, target, source)