[알고리즘] 재귀 알고리즘(Recursive Algorithms)

이번에는 재귀 알고리즘에 대해서 알아보려고 합니다 :-)

재귀 알고리즘

• 재귀 알고리즘: 일반적으로 재귀 함수에 의해서 구현
• 재귀함수(recursive functions): 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
• 생각보다 많은 종류의 문제가 재귀적으로 해결 가능

예시

• 이진트리 (binary trees)

  • 왼쪽 서브트리의 원소들은 모두 작거나 같을 것
  • 오른쪽 서브트리의 원소들은 모두 클 것
    위 원칙을 모든 노드에 대해서 적용한 것을 재귀 알고리즘으로 구현 가능

• 자연수의 합 구하기

  • 문제: 1부터 n까지 모든 자연수의 합 구하기

$S=\sum_{k=1}^{n} k ->S=n+\sum_{k=1}^{n-1}k$
오른쪽 수식을 아래와 같이 구현 가능

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

자연수의 합 구하는 것을 재귀 알고리즘을 활용하여 구현

def sum(n):
	if n <= 1:
    	return n
    else:
		return n + sum(n-1)
    
a = int(input("Number: "))
print(sum(a))

재귀 함수 호출 시 종결 조건 매우 중요!!!!!!
알고리즘의 종결조건에 반드시 필요하므로 주의 필요

재귀 알고리즘의 효율

# Recursive version
def sum(n):
	if n <= 1:
    	return n
    else:
		return n + sum(n-1)

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

• 알고리즘의 복잡성은 둘다 $O(n)$로 동일하다.
• 알고리즘의 효율성 측면에서 보면 Recursive version은 매번 함수를 호출하기 때문에 효율성이 떨어진다.
• 재귀 알고리즘이 항상 유리한 것이 아니므로 주의가 필요하다!!!

예제

• factorial 구현하기

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