3. Recursion

Recusion

재귀: 자기 자신을 호출하는 함수

자신의 복사본을 호출하여 더 작은 문제를 풀게함으로써 문제를 해결합니다. 이를 재귀 단계라고 하는데, 재귀 단계는 더 많은 수의 재귀 단계를 만들 수 있습니다. 매 단계보다 함수는 원본 문제보다 조금 더 단순한 문제를 가지고 자기 자신을 호출합니다.

• 재귀를 사용하여 문제를 해결할 때 아이디어는 큰 문제를 더 작고 유사한 문제로 만듭니다.
• 결국이 프로세스가 반복되고 문제의 크기가 각 단계에서 감소하면 매우 작고 해결하기 쉬운 문제에 도달합니다.

 

void recursiveFunction (int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num+1);
}

n = 0 일때

 

결과

 

구성

1. base case: 비 재귀적으로 기술 될 수있는 기본 사례
2. recursive case: 해가 자신의 더 작은 버전으로 표현 될 수있는 재귀적인 경우.

 

예시1. Factorial

factorial(n)

function factorial

input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1
2. otherwise, return [ n × factorial(n-1) ]

end factorial 

 

$$\begin{align} factorial(n=4) \\ f_4 & = 4*f_3 \\ & = 4 * (3 * f2) \\ & = 4 * (3 * (2 * f1)) \\ & = 4 * (3 * (2 * (1 * f0))) \\ & = 4 * (3 * (2 * (1 * 1))) \\ & = 4 * (3 * (2 * 1)) \\ & = 4 * (3 * 2) \\ & = 4 * 6 \\ & = 24 \end{align} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$

 

 

예시 2. GCD (Great common divisor)

gcd(x, y)

function gcd
input: iteger x, y such taht x >=y, y>0
output: gcd of x and y
1. if y is 0, return x
2. otherwise, return [gcd (y, x%y)]

end gcd

 

$$\begin{align} gcd(259, 111) \\ & gcd (259,111) \\ = & gcd(111, 259\% 111) \\ = & gcd(111, 37) \\ = & gcd(37, 111\%37) \\ = & gcd(37,0) \\ = & 37 \\ \end{align} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

 

예시 3. Recursive binary search

정렬된 int 배열에서 특정 값을 검색합니다. 예 : {-3, -2, 0, 0, 1, 5, 5}.

배열에서 1(target)을 검색하려고합니다. 1(target)을 찾으면 배열 인덱스를 반환합니다. 그렇지 않으면 FAILURE (-1)을 반환합니다.

 

• base case:
  • target 값이 배열안에 존재하지 않을 때
  • target 값을 찾았을 때
• recursive case:

 

code

int binarySearch(int list[], int target, int left, int right) {
    if (left > right) return FAILURE; // base case
    
    mid = (left + right)/2; 
    
    if (target == list[mid]) return mid; // base case
    
    if (target < list[mid])
        return binarySearch(list, target, left, mid-1); // recursive
    
    else
        return binarySearch(list, target, mid+1, right); // recursive
}

 

$$\begin{align} 시간복잡도: \ log_2n \end{align} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

 

예시 4. 하노이 타워

세 개의 축과 n개의 원반이 주어지는데 각각의 원반은 크기가 상이합니다. 축을 A, B, C라고 부르기로 하고 원반은 가장 작은 원반을 1로, 가장 큰 원반을 n이라고 번호를 매긴다고 합시다. 처음에는 모든 n개의 원반이 크기 순서대로 위에서 아래로, 즉 1이 가장 위에, 그리고 n이 가장 아래인 상태로 축 A에 놓여 있습니다. 원반이 5개인 하노이 탑은 다음과 같습니다.

목표는 모든 n개의 원반을 축 A에서 축 B로 옮기는 것입니다.

1. 한 번에 하나의 원반만 움직일 수 있습니다.
2. 자신보다 작은 원반이 그 아래에 놓일 수 없습니다. 예를 들어 원반 3이 축에 있다면 원반 3 밑에 있는 원반은 모두 3보다 큰 숫자로 되어 있어야 합니다.

 

알고리즘

1. 크기가 1부터 n-1인 디스크들을 A에서 B로 이동시킵니다.
2. 나머지 가장 큰 디스크를 A에서 C로 이동시킵니다.
3. 크기가 1부터 n-1인 디스크들 B에서 C으로 이동합니다.

• Base case: 크기가 1인 디스크를 옮길 때
• Recursive algorithm: 크기가 2 이상인 디스크를 옮길 때

 

코드

void hanio (int n, char from, char inter, char to) {
    if (n == 1) printf("Disk 1 from %c to %c\n", from , to);
    else {
        hanoi(n-1, from, to, inter);
        printf("Disk %d from %c to %c\n", n, from, to);
        hanoi(n-1, inter, from, to);
    }
}

 

효율성

N개의 원반이 있을 때 총 몇 번 이동시켜야 할까?

1. 상위 n-1 디스크를 A에서 B로 이동시킵니다. hanoi(n-1) move
2. 나머지 (가장 큰) 디스크를 A에서 C로 이동시킵니다. hanoi(1) move
3. n-1 디스크를 B에서 C으로 이동합니다. hanoi(n-1) move

번원반을움직여야한다

$$\begin{align} hanoi(4) \\ & = 2 * hanoi(3) + 1 \\ & = 2 * (2*hanoi(2) + 1) + 1 \\ & = 2 * (2 * (2*hanoi(1) + 1) + 1) + 1 \\ & = 2 * (2 * (2*1) + 1) + 1) + 1 \\ & = 2 * (2 * (3) + 1) + 1 \\ & = 2 * (7) + 1 \\ & = 15 \end{align} \ \ \ \ \ \ \ \ \ \ \ \ \ 2^n - 1 번\ 원반을\ 움직여야\ 한다.$$

예시 5. Fibonacci

예시 6. Binomial coefficents

 

 

재귀는 좋은가?

• Faster? 일반적으로 스택을 유지하는 오버헤드 때문에 더 느립니다.
• Less memory? 스택을 사용하기 때문에 더 많은 메모리를 사용합니다.

=> 그럼에도 불구하고 문제해결을 더욱 간단히 할 수 있기 때문에 사용합니다.