3. 재귀 알고리즘 기초 및 응용

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉

 

 

 

재귀 함수(Recursive Functions)

• 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
• ex) 이진 트리(binary trees)

 

알고리즘들 중에는, 재귀 알고리즘 (recursive algorithm) 이라고 불리는 것들이 있다. 이것은 알고리즘의 이름이 아니라 성질이다.

주어진 문제가 있을 때, 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용해서, 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법이다.

 

예를 들면, 1 부터 n 까지 모든 자연수의 합을 구하는 문제 (sum(n))는, 1 부터 n - 1 까지의 모든 자연수의 합을 구하는 문제 (sum(n - 1))를 풀고, 여기에 n 을 더해서 그 답을 찾을 수 있다. 즉, sum(n) = sum(n - 1) + n이다.

생각보다 많은 종류의 문제들이 재귀적으로 (recursively) 풀린다.

def sum(n):
# print(n)
	if n <= 1: // 재귀 호출의 종결 조건
    		return n
    	else:
        	return n + sum(n-1)

        a = int(input("Number: "))
        print(sum(a))

위의 sum(n) 을 구하는 문제를 재귀적으로 해결하기 위해서는, 그 종결 조건 (trivial case) 을 명시해야 한다.

위 수식 (수학에서는 "점화식" 이라는 용어를 사용한다.) 이 자연수들의 합을 구하는 문제를 푸는 데 적용될 수 있으려면, 무한히 n - 1 까지의 합을 적용해서는 안되고, 언젠가는 이에 대한 답을 주어야 한다.

1 부터 1 까지의 모든 자연수의 합은 1 이므로, 위 점화식에 덧붙여 하나의 수식을 추가해야 한다: sum(1) = 1. 이 두 수식을 묶으면, 1 부터 n 까지의 자연수의 합을 구하는 문제의 답이 된다. 이것이 재귀 알고리즘 (recursive algorithm) 이다.

 

def solution(x):
    if x < 2: 
        return x
    
    answer = solution(x-1) + solution(x-2)
    return answer

 

많은 경우, 재귀적으로 표현된 알고리즘은 사람이 이해하기는 좋지만, 컴퓨터가 알고리즘을 실행하면 그 성능도 좋을까? 

 

• O(n) 보다 O(1) 더 효율적이다.

 

얼핏 생각하는 것보다 많은 문제들이 재귀적인 방법으로 풀어진다.

• 조합의 수 (n 개의 서로 다른 원소에서 m 개를 택하는 경우의 수) 구하기
• 하노이의 탑 (크기 순서로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기)
• 피보나치 순열

문제의 종류에 따라서는 재귀 알고리즘을 적용함으로써 알고리즘을 간단하고 이해하기 쉽게 서술할 수 있다는 장점이 있다. 그런데, 문제를 풀어 내는 데 걸리는 시간 측면에서는 어떨까?

하나의 재귀 알고리즘이 주어질 때, 이것을 재귀적이지 않은 (non-recursive) 방법으로 동일하게 풀어내는 알고리즘이 존재한다는 것을 수학적으로 증명할 수 있다. 보통은 순환문 (loop) 을 이용해서 정해진 연산을 반복함으로써 문제의 답을 구하는데, 따라서 반복적 (iterative) 알고리즘이라고 부르기도 한다.

일반적으로, 주어진 문제에 대해서 반복적인 알고리즘이 재귀적인 알고리즘보다 문제 풀이의 (시간적) 효율이 높다.

그럼에도 불구하고, 재귀 알고리즘이 가지는 특성 때문에 트리 (tree) 와 같은 자료 구조를 이용하는 알고리즘에는 매우 직관적으로 적용할 수 있는 경우가 많다.

---

[문제 1] 피보나치 순열

def solution(x):
    if x < 2: 
        return x
    
    answer = solution(x-1) + solution(x-2) 
    return answer

 

[문제 2] 재귀적 이진 탐색 구현하기

def solution(L, x, l, u):
    if l > u:             # lower가 upper보다 크면 List길이는 0
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid -1) # 가존upper값은 mid기준으로 다음값은 무의미

    else:
        return solution(L, x, mid+1, u) # 기존lower값은 mid기준으로 그전값은 무의미