[알고리즘] 재귀

재귀란, 함수 내부에서 자기 자신을 호출하는 방법입니다.

가장 대표적인 예제인 팩토리얼을 통해 작동하는 원리를 알아봅시다.

먼저, 반복문으로도 팩토리얼을 계산할 수 있습니다.

def factorial(n):
   value = 1
   for i in range(1, n+1):
       value *= i
   return value

이를 재귀를 이용해 구현하면 다음과 같습니다.

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

위 코드를 보면, n이 1보다 클 경우 factorial(n-1)이라는 코드에서 자기 자신을 호출하는 것을 확인할 수 있습니다. 이를 '함수를 재귀적으로 호출한다'라고 표현합니다. 위 코드는 다음과 같이 작동할 것입니다.

n부터 시작해서, n=1이 될 때까지 재귀적으로 함수를 호출한 뒤에 차례대로 return값을 반환하는 것을 볼 수 있습니다.

 

알고리즘 문제해결 과정에서, 재귀는 가능한 경우의 수를 체계적으로 탐색할 때 사용됩니다. 크게 3가지 경우에 많이 쓰입니다.

1. 부분집합 생성

임의의 집합 {1,2,3}의 부분집합은 ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}으로 총 8개입니다. 이번 예시 같은 경우는 원소가 3개인 작은 집합이라 간단하게 파악할 수 있었지만, 원소의 개수가 많아진다면 재귀적인 탐색을 통해 그 경우의 수와 각 부분집합을 찾을 수 있습니다.

# subset : 부분집합 저장하는 리스트, n=원소 개수

def search(k):
    if k==n+1:
        # 부분집합을 처리한다
    else:
        subset.append(k)
        search(k+1)
        subset.pop()
        search(k+1)

이 코드를 그림으로 나타내면 다음과 같습니다.

사실, 원소 n개를 가진 집합의 부분집합의 개수는 2^n개라는 것을 잘 알 것입니다. 이는 부분집합에 각 원소를 넣거나 넣지 않는 옵션이 있기 때문이고, 이를 n개의 원소 각각에 모두 적용하면 2 x 2 ... 2 x 2 = 2^n개가 된다는 것을 알 수 있습니다.

재귀를 이용해 부분집합에서 각 원소를 넣었다가 뺄 수 있습니다. 위 코드를 보면 부분집합에 원소 k를 넣은 후 재귀적으로 search(k+1)을 호출한 다음, 부분집합에서 원소 k를 빼고 다시 재귀적으로 search(k+1)을 호출하는 것을 볼 수 있습니다. 이처럼 재귀적인 탐색을 통해 집합의 부분집합을 탐색할 수 있습니다.

2. 순열 생성

임의의 집합 {1,2,3}의 순열은 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)으로 총 6개입니다. 이를 일반화하면 원소가 n개인 집합의 수열은 n!개라고 할 수 있습니다.

재귀적으로 순열을 생성하는 과정은 부분집합을 생성하는 방법과 상당히 유사합니다.

# chosen : 순열에 요소 존재하는지 체크하는 리스트, seq : 순열 저장하는 리스트

def search():
    if len(seq) == n:
        # 순열을 처리한다
    else:
        for i in range(1, n+1):
            if chosen[i] == true:
                continue
            chosen[i] = True
            seq.append(i)
            search()
            chosen[i] = False
            seq.pop()

임의의 수열 seq에 원소를 넣었다 뺐다 하는 과정은 비슷하지만, 부분집합과는 달리 결국에는 모든 원소가 순열에 들어가야 하기 때문에 반복문으로 모든 원소를 집어넣는 것을 확인할 수 있습니다.

3. 백트래킹(퇴각 검색)

이처럼 재귀는 경우의 수를 탐색하는 데 유용하게 쓰일 수 있습니다. 다만, 어떤 경우에는 같은 것을 기하급수적으로 많이 반복하게 되어 코드가 비효율적으로 작동할 수도 있습니다. 대표적인 예제인 피보나치 수열을 통해 알아보도록 합시다.

피보나치 수열의 정의

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

위 코드처럼 재귀적으로 피보나치 수열을 구할 수 있습니다. 하지만 이 코드는 매우 비효율적으로 작동하는데요, f(n)을 계산하기 위해 f(n-1)과 f(n-2)의 값을 알아야 하지만 위 코드를 이용하면 매번 피보나치 수열의 값을 다시 계산해야 하기 때문에 연산 횟수가 기하급수적으로 증가합니다. (fibonacci(35)를 위 코드로 계산한다면 약 1800만 번의 덧셈 연산을 하게 됩니다)

 

이러한 단점을 보완하기 위해 메모화(memoization)이라는 기법을 사용하는데요, 이는 한 번 계산된 값을 저장해서 이후에 다시 계산하지 않고 저장된 값을 활용하는 방법입니다. 메모화를 사용하면 더 효율적인 재귀적 탐색이 가능해집니다.

fibo = [0 for _ in range(n+1)]
fibo[1] = 1
fibo[2] = 1

def fibonacci(n):
    if fibo[n] > 0:
        return fibo[n]
    else:
        fibo[n] = fibonacci(n-1) + fibonacci(n-2)
        return fibo[n]

위 코드를 살펴보면, fibo[n]의 값을 이미 알고 있는 상태라면 저장된 값을 반환하고, 값을 모른다면 재귀적 호출을 통해 값을 계산해 반환한다는 것을 알 수 있습니다. 메모화를 사용하지 않을 때보다 훨씬 효율적으로 작동한다는 느낌이 오지 않나요?

 

메모화는 동적 프로그래밍(Dynamic Programming, DP)에서 더 자세히 다룹니다.

 

< 참고자료 >

- 알고리즘 트레이닝 (안티 라크소넨, 프로그래밍 인사이트)