떡국 = (떡국떡)국 = ((떡국떡)국떡)국... [재귀프로그램]

재귀 프로그램은 어떤 함수(Procedure)가 어떤 함수를 반복해서 호출하는 경우 생기는 순환적 특성을 이용한 프로그램을 의미한다. 같은 해결법을 반복해서 수행하며, 보통 큰 문제로부터 수행 단계가 깊어질수록 작은 문제로 쪼개 해결하는 방식을 취하기 때문에 분할 및 정복(Divide and Conquer)이라고 할 수 있다. 재귀 구조는 반복(for문) 문을 이용한 구조로 바꿀 수 있다.

 

재귀 구조와 반복 구조를 비교해보면, 재귀 구조의 경우 코드가 간단하고 명료해질 수 있다는 장점이 있으나, 반복적 함수 호출을 위한 시간적 오버헤드 및 함수 호출 스택이 필요하다는 등의 공간적 오버헤드가 발생한다.

 

백문이 불여일견이라고, 말이 긴 것보다 예제를 보는 것이 빠를 수도 있다. 대표적인 예로는 피보나치수열이 있다. 이참에 직접 코드를 작성해보도록 하자.

---

1. 피보나치수열

f(0) = 0, f(1) = 1이고, n > 1인 자연수 n이 주어졌을 때 f(n) = f(n-1) + f(n - 2)

반복

n = input()
result = 0
n_2 = 0
n_1 = 1
for i in range(n + 1):
    if i <= 1:
        result = i
        continue
    result = n_1 + n_2
    n_2 = n_1
    n_1 = result
print(result)

 

반복문을 통한 n번째 피보나치 수열 구하기

• n번째 피보나치 수를 구하기 위한 n(0이상의 정수)을 입력받는다.
• n이 1 이하일 경우 result = n
• n이 2 이상일 경우 f(n-1)=1, f(n-2)=2로 시작
• 2부터 n까지 반복한다.
  
  • f(n-1) + f(n-2)를 더한 값을 result에 저장
  • f(n-2) = f(n-1), f(n-1) = f(n)을 수행
• 결과값을 출력한다.

n = 5일 경우 해당 코드의 수행과정을 나타내 보면(각 i에 대해 반복문 시작 -> 종료 시 상태)

i	result	n-1	n-2
0	0 -> 0	1	0

i	result	n-1	n-2
1	0 -> 1	1	0

i	result	n-1	n-2
2	1 -> 1	1 -> 1	0 -> 1

i	result	n-1	n-2
3	1 -> 2	1 -> 2	1 -> 1

i	result	n-1	n-2
4	2 -> 3	2 -> 3	1 -> 2

i	result	n-1	n-2
5	3 -> 5	3 -> 5	2 -> 3

이와 같은 수행 과정을 거친다.

 

이때, 시간 복잡도는 n에 대해 O(n)이다. n의 입력에 따라 n번 for문을 돌며(정확히는 0부터 n까지 n + 1번이나, O(n) = O(n + 1)) 계산하기 때문이다.

재귀

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

 

재귀 문을 통한 n번째 피보나치수열 구하기

• n번째 피보나치수를 구하기 위한 함수를 정의한다.
• f(1) = 1, f(0) = 0이므로, n이 1이하일 경우 함수는 n값을 반환한다.
• n이 1보다 클 경우 f(n-1) + f(n-2)를 수행한다.
• 이를 그림으로 나타내면 다음과 같다. (n이 5일 경우)
•  [(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5)]

f(5) = 5
f(4) = 3					f(3') = 2
f(3) = 2			f(2') = 1		f(2'') = 1			f(1'''') = 1
f(2) = 1		f(1') = 1	f(1'') = 1	f(0') = 0	f(1''') = 1		f(0'') = 0
f(1) = 1	f(0) = 0

이때, return이 이루어지는 순서는 나중에 다룰 이진트리의 순회 중 후위 순회(Postorder) 순서이다.

즉, 이 과정에서 f(n)은 스택에 순서대로 쌓이는 일종의 깊이 우선 탐색을 수행하게 되는데, 이를 나타내 보면

 

입력 n = 5 -> f(5)

f(5)

f(5) = return f(4) + f(3)

f(4)

f(5)

f(4) = return f(3) + f(2')

f(3)

f(4)

f(5)

f(3) = return f(2) + f(1')

f(2)

f(3)

f(4)

f(5)

f(2) = return f(1) + f(0)

f(1)

f(2)

f(3)

f(4)

f(5)

f(1) = return 1

f(2')

f(3)

f(4)

f(5)

f(2) = return 1 + f(0)

f(0)

f(2)

f(3)

f(4)

f(5)

f(0) = return 0

f(2)

f(3)

f(4)

f(5)

f(2) = return 1 + 0

f(3)

f(4)

f(5)

f(3) = return 1 + f(1')

f(1')

f(3)

f(4)

f(5)

f(1') = return 1

f(3)

f(4)

f(5)

f(3) = return 1 + 1

f(4)

f(5)

f(4) = return 2 + f(2')

f(2')

f(4)

f(5)

f(2') = return f(1'') + f(0')

f(1'')

f(2')

f(4)

f(5)

f(1'') = return 1

f(2')

f(4)

f(5)

f(2') = return 1 + f(0')

f(0')

f(2')

f(4)

f(5)

f(0') = return 0

f(2')

f(4)

f(5)

f(2') = return 1 + 0

f(4)

f(5)

f(4) = return 2 + 2

f(5)

f(5) = return 4 + f(3')

f(3')

f(5)

f(3') = return f(2'') + f(1'''')

f(2'')

f(3')

f(5)

f(2'') = return f(1''') + f(0'')

f(1''')

f(2'')

f(3')

f(5)

f(1''') = return 1

f(2'')

f(3')

f(5)

f(2'') = return 1 + f(0'')

f(0'')

f(2'')

f(3')

f(5)

f(0'') = return 0

f(2'')

f(3')

f(5)

f(2'') = return 1 + 0

f(3')

f(5)

f(3') = return 1 + f(1'''')

f(1'''')

f(3')

f(5)

f(1'''') = return 1

f(3')

f(5)

f(3') = return 1 + 1

f(5)

f(5) = return 4 + 1

 

따라서 f(5) = 5이다.

 

딱 봐도 코드는 반복 구조에 간단해 보여도 계산 과정은 훨씬 복잡해 보인다. 이때, 시간 복잡도는 n에 대해 O(nlogn)이다. 왜냐하면 함수 호출 스택 깊이는 n만큼이고, f(n)을 f(n-1)과 f(n-2)로 나누어 계속해서 함수 호출이 2배로 늘어나기 때문에 가장 깊은 곳에서의 호출 함수 개수는 2^n-1이며, 그 전 단계의 깊이는 2^n-2 ... 이런 식으로 log₂n의 형태가 되고, 결국 이는 각 단계에서약 log₂n 만큼의 호출이 이루어지는 것을 의미한다. 즉 n번의 스택 단계에서 각 단계마다 약 log₂n 만큼의 계산이 이루어지므로 대략적인 시간 복잡도 표현은 f(n) = n * log₂n 이고, 이를 Big-O로 나타내면 최고 차수의 표현만 하면 되므로 O(nlogn)이 된다.

 

같은 결과를 내는데 왜 반복 구조로 할 경우 O(n)이지만 재귀 구조일 경우 O(nlogn)이 될까? 이는 알고리즘에서 다룰 동적 계획법(Dynamic Programming)과 조금은 관련이 있는데, 반복 구조의 경우 이전 단계의 계산을 n-1과 n-2라는 변수에 저장해서 다음 단계에 이용하고 같은 계산을 또 하지 않았지만, 재귀 구조의 경우 f(5)를 계산해내기 위해 f(2)에 대한 계산만 3번이나 이루어지는 것을 볼 수 있다. 이러한 점을 참고해두면 좋다.