[알고리즘] 재귀 알고리즘 응용

지난번에 간단하게 재귀 알고리즘에 대해서 알아보았는데 이번에는 조금 더 자세히 알아보려고 한다!

재귀 알고리즘 응용

• 재귀함수(recursive function): 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수

재귀 알고리즘의 효율성 (조합의 수 계산)

조합의 수 계산 예시를 통해 재귀 알고리즘의 효율성에 대해 알아볼 것이다.

• 문제: n개의 서로 다른 원소에서 m개를 택하는 경우의 수
  $\frac{n!}{m!(n-m)!}$
• 위 문제를 factorial 함수를 활용하여 구현하면 다음과 같다.

from math import factorial as f
def combi(n, m):
	return f(n)/(f(m)*f(n-m))

• 이번에는 위 문제를 재귀 알고리즘 문제로 변환을 한다.
  • 원 문제: n개의 서로 다른 원소에서 m개를 택하는 경우의 수
  • 재귀 알고리즘 문제: n-1개의 서로 다른 원소에서 m개를 택하는 경우의 수 + n-1개의 서로 다른 원소에서 m-1개를 택하는 경우의 수
  • 위 두 문제가 같은 이유는 특정한 하나의 원소 입장에서 볼 때, 이 원소를 포함하는 경우와 그렇지 않은 경우를 따로 계산해서 더하기 때문이다.
• 재귀 알고리즘을 활용하여 구현하면 다음과 같다.

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
    else:
    	return combi(n-1, m) + combi(n-1, m-1)

• 위 코드를 효율성 측면에서 보면 한 함수당 함수를 두번씩 return하고 있기 때문에 n이 커지면 함수가 너무 많이 호출 된다.
• 따라서 반복문을 활용하는 것이 더 좋은 방법이 될 수 있다.

효율이 떨어지는 데 왜 재귀 함수를 사용하나.

재귀 알고리즘의 유용성

재귀 알고리즘은 항상 효율성이 떨어지는 것은 아니다. 다음은 재귀 알고리즘이 유용한 경우이다.

• 문제: 하노이의 탑
  기둥에 크기가 다른 원반들이 있고 한 기둥의 원반들을 다른 기둥으로 옮기는 것 (큰 원반을 더 작은 원반에 올릴 수 없다)
  이것을 재귀적 알고리즘으로 구현하면 매우 쉽다.

피보나치 함수

피보나치 함수를 재귀 알고리즘을 사용했을 때와 반복문을 활용 했을 때를 비교해 본다.

• 재귀 알고리즘 활용
  • fibo(4) 함수 사용 시 도합 9번의 함수가 호출된다.
  • 따라서 매우 비효율적이다.

def fibo(n):
	if n <= 1:
    	return n 
    return fibo(n-1) + fibo(n-2)

• 반복문 활용

def fibo_iter(n):
 	if n <= 1: 
    	return n
    else:
    	i = 2
        t0 = 0
        t1 = 1
        while i <= n:
        	t0, t1 = t1, t0 + t1
            i += 1
        return t1