재귀 알고리즘은 함수가 자신을 호출하여 원래 문제의 더 작은 버전을 해결하는 알고리즘 접근 방식입니다. 다시 말해, 문제는 원래 문제와 동일한 성질을 가지지만 어떤 면에서는 더 단순한 작은 하위 문제로 분할됩니다. 이 하위 문제 각각은 같은 함수를 호출하여 해결되며, 이 과정은 문제가 직접적으로 해결될 수 있는 충분히 작은 크기가 될 때까지 계속됩니다(기본 사례).
재귀 알고리즘의 기본 구성 요소는 다음과 같습니다:
기본 사례: 문제를 직접적으로 해결할 수 있는 가장 간단한 형태의 조건입니다. 추가적인 재귀를 방지하고 멈춤 기준으로 작용합니다.
재귀 사례: 함수가 자신을 호출하여 원래 문제의 더 작은 버전을 해결하는 부분입니다.
재귀 알고리즘을 구현할 때 기본 사례가 명확하게 정의되어야 하며, 재귀 사례가 기본 사례를 향해 진행하도록 해야 합니다. 그렇지 않으면 알고리즘은 무한 재귀에 빠져 스택 오버플로우를 발생시킬 수 있습니다.
예시: 재귀 알고리즘(팩토리얼)
재귀 알고리즘의 대표적인 예로, 비음수 정수의 팩토리얼을 계산하는 것이 있습니다. 비음수 정수 n의 팩토리얼은 n!으로 표기되며, 1부터 n까지의 모든 양의 정수를 곱한 값을 의미합니다.
def factorial(n):
if n == 0:
return 1 # 기본 사례: 0!은 1입니다.
else:
return n * factorial(n - 1) # 재귀 사례: n! = n * (n-1)!
이 재귀적인 구현에서 factorial() 함수는 인자로 n - 1을 갖고 자신을 호출합니다(더 작은 하위 문제). 이 과정은 n이 0이 될 때까지 계속됩니다. 이때 기본 사례가 발동되며 0의 팩토리얼은 1로 정의되어 재귀가 멈춥니다.
재귀 알고리즘은 분할 정복 구조를 자연스럽게 가지는 문제에 우아하고 표현적인 해결책일 수 있습니다. 하지만 불필요한 계산을 포함하거나 호출 스택 때문에 더 많은 메모리를 사용할 수 있어서 항상 가장 효율적인 선택은 아닐 수 있습니다. 이런 경우에는 반복적이거나 다른 알고리즘 접근 방식이 더 적합할 수 있습니다.
재귀 함수를 이용해서 아래와 같이 유클리드 호제법을 이용한 최대공약수를 구하는 함수를 만들어 보겠습니다.
유클리드 호제법 Euclidan Algorithm
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
즉, gcd(a, b) = gcd(b, r)
def gcd(n1, n2):
if n1 % n2 == 0: # 기본 사례
return n2
else:
return gcd(n2, n1 % n2) # 재귀 사례
