재귀 알고리즘

김서연·2024년 3월 29일

자료구조 & 알고리즘

목록 보기

4/15

1 재귀 알고리즘 기초

1.1 재귀함수(recursive function)란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
생각보다 많은 종류의 문제가 재귀적으로(recursively) 해결 가능
재귀: 꼬리에 꼬리를 문다는 것

1.2 예시

1.2.1 이진트리(binary trees)

이진트리는 두 개의 서브트리를 자식으로 갖는데, 왼족 서브트리의 원소들은 모두 작거나 같아야 하고, 오른쪽 서브트리의 원소들은 모두 커야한다
→ 이 원칙을 모든 노드에 대해서 적용
이진트리를 탐색할 때도 재귀함수를 적용 가능
이진탐색과 비슷한 구조

1.2.2 자연수의 합 구하기

문제: 1부터 n까지의 모든 자연수의 합을 구하시오

def sum(n):
	return n + sum(n-1)

→ 위 코드를 실행하면 오류가 난다

별도의 장치 없이 재귀함수를 실행하면 무한히 실행하게 되므로 종결 조건이 필수적으로 필요하다

1.3 종결 조건

4.2.2에서 구현한 코드에 종결 조건을 추가한 코드이다
문제에서 1 ~ n을 더하는 것이었으므로 1이하일 때를 종결 조건으로 추가해 주었다

def sum(n):
	# 종결 조건
	if n <= 1: return 1
	else:	return n + sum(n-1)

위 코드를 실행하면 무사히 작동하는 것을 확인할 수 있다

1.4 재귀 알고리즘의 효율

모든 재귀알고리즘은 그와 대칭되는 반복적인 알고리즘이 있다
즉, 재귀 알고리즘은 for, while과 같은 반복문을 통해 구현이 가능하다
재귀 알고리즘은 Recursive version, 반복문을 활용한 것은 Iterative version 이라고 한다

Recursive version

def sum(n):
    # 종결 조건
    if n <= 1: return 1
    else:	return n + sum(n-1)

→ $O(n)$

Iterative version

def sum(n):
    s = 0
    while n >= 0:
        s += n
        n -= 1
    return s

→ $O(n)$

시간 복잡도가 아닌 효율성 측면에서 재귀 알고리즘은 함수를 호출할 수록 메모리를 차지하기 때문에 iterative version보다 떨어진다 (counter part)
수학 공식을 활용하면 상수 시간의 코드를 얻을 수 있다
```
def sum(n):
    return n * (n+1) // 2
```
→ $O(1)$

1.5 추가 예제

1.5.1 팩토리얼

def what(n):
	if n <= 1:
		return 1
	else:
		return n * what(n-1)

→ 1부터 n까지 곱한다 ⇒ $n!$

팩토리얼은 개념 자체가 재귀적이기 때문에 재귀함수를 이해하기에 좋다

1.5.2 Fibonacci 순열

recursive version

def fib(n):
    if n <= 0: return 0
    elif n <= 2: return 1
    else: return fib(n-2) + fib(n-1)

iterative version

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    return a

2. 재귀 알고리즘 응용

2.1 조합의 수 구하기

문제: n개의 서로 다른 원소에서 m개를 택하는 경우의 수

공식을 활용하는 방법

$\binom{n}{m} = \frac{n!}{m!(n-m)!}$
```
from math import factorial as f

def combi(n, m):
	return f(n) / (f(m) * f(n-m))
```

재귀적 방법으로 구하기

$\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}$
- n-1개의 서로 다른 원소에서 m개를 택하는 경우의 수와 n-1개의 서로 다른 원소에서 m-1개를 택하는 경우의 수를 더한 것과 같다
- 즉, n-1개의 1개를 포함해 고르는 경우(n-1개 중 m-1), 포함하지 않고 고르는 경우(n-1개 중 m개)를 따로 계산하는 것
```
# Trivial case를 고려하지 않은 코드
def combi(n, m):
	return combi(n-1, m) + combi(n-1, m-1)
```
```
# Trivial case를 고려한 코드
def combi(n, m):
	# 모든 것을 골라야하는 경우
	if n == m: return 1
	# 고를 것이 없는 경우
	elif m == 0: return 1
	return combi(n-1, m) + combi(n-1, m-1)
```
- combi()를 두 번 호출하기 때문에 효율성 측면에서 좋지 않다
  
  → iterative version이 더욱 효율적인 경우

2.2 하노이의 탑

재귀적으로 생각하고 코드를 작성하기 쉬운 문제
트리처럼 재귀 알고리즘이 더욱 좋은 경우가 있기 때문에 문제에 따라 재귀 알고리즘을 사용하면 좋다

2.3 피보나치 순열

# 수업에서 나온 코드
def fib(n):
    elif n <= 2: return n
    else: return fib(n-2) + fib(n-1)

동일한 작업이 여러번 발생한다는 비효율적인 측면이 있다
→ 숫자가 커질수록 iterative version이 더 효율적이다

2.4 재귀적 이진 탐색

def binsearch(L, x, lower, upper):
	if upper < lower:
		return -1
	middle = (lower + upper)//2
	if x == L[mid]:
		return mid
	elif x < L[mid]:
		return binsearch(L, x, lower, middle-1)
	else:
		return binsearch(L, x, middle+1, upper)