오늘은 이전 포스팅에서 다뤘던 유클리드 호제법을 학습하면서 궁금했던 재귀 함수에 대해 공부해 보겠습니다.
특히, 유클리드 호제법의 구현에서 재귀 함수가 어떻게 작동하는지, 그리고 재귀 함수의 기본 원리와 장단점에 대해 살펴보겠습니다.
재귀 함수란?
재귀 함수는 자기 자신을 호출하는 함수입니다. 큰 문제를 작은 문제로 나눠서 해결하는 방식으로, 특히 수학적 정의를 코드로 표현하거나 트리 탐색과 같은 알고리즘에서 자주 사용됩니다.
재귀 함수의 기본원리
재귀 함수는 두 가지 주요 요소로 이루어집니다.
- 기저 조건 (Base Case)
- 재귀를 멈추는 조건으로 무한 루프를 방지합니다.
- 재귀 조건 (Recursive Case)
- 문제를 더 작게 쪼개기 위해 자기 자신을 호출하는 부분입니다.
재귀 함수가 호출될 때, 각 호출은 스택 메모리에 쌓입니다. 기저 조건을 만나면 스택에서 하나씩 반환되며 작업이 종료됩니다.
*스택 메모리: 프로그램 실행 중 함수 호출과 관련된 정보를 저장하는 메모리 공간입니다.
재귀를 이용한 유클리드 호제법
이전에 포스팅했던 유클리드 호제법에서 재귀 함수를 사용해 구현해 봤습니다.
public class GCDRecursive {
public static int gcd(int a, int b) {
if (b == 0) { // 기저 조건: 나머지가 0일 경우, a가 최대공약수
return a;
}
return gcd(b, a % b); // 재귀 호출: b와 a % b로 문제를 작게 나눔
}
public static void main(String[] args) {
int result = gcd(48, 18);
System.out.println("48과 18의 최대공약수(GCD) = " + result);
}
}출력 결과:
48과 18의 최대공약수(GCD) = 6재귀 호출 과정
위 코드의 실행 흐름을 살펴보면 다음과 같습니다:
gcd(48, 18)→ 호출,a = 48,b = 18gcd(18, 12)→ 호출,a = 18,b = 48 % 18 = 12gcd(12, 6)→ 호출,a = 12,b = 18 % 12 = 6gcd(6, 0)→ 기저 조건 도달,b = 0→ 최대공약수6반환
스택 메모리 상태
- 각 호출은 스택에 쌓입니다:
gcd(48, 18)gcd(18, 12)gcd(12, 6)gcd(6, 0)→ 반환 시작
- 이후 반환하며 호출을 정리:
gcd(12, 6)→ 6 반환gcd(18, 12)→ 6 반환gcd(48, 18)→ 6 반환
재귀 함수와 반복문의 비교
위 유클리드 호제법은 반복문으로도 구현할 수 있습니다. 동일한 알고리즘을 반복문으로 구현해 보겠습니다.
public class GCDIterative {
public static int gcdIterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
int result = gcdIterative(48, 18);
System.out.println("48과 18의 최대공약수(GCD) = " + result);
}
}
출력 결과는 동일합니다.
반복문 vs 재귀 함수
| 비교 항목 | 재귀 함수 | 반복문 |
| 가독성 | 수학적 정의에 충실, 간결하고 직관적 | 기계적인 느낌이지만 이해하기 쉬움 |
| 성능 | 호출 스택을 사용해 약간의 오버헤드 발생 | 스택 메모리를 사용하지 않아 효율적 |
| 호출 깊이 | 깊어지면 StackOverflowError 위험 존재 | 깊이에 상관없이 안전하게 동작 |
| 적합한 상황 | 트리 탐색, 수학적 정의 문제 등 직관성이 중요한 경우 | 성능 최적화가 필요한 반복적 작업에 적합 |
재귀 함수는 언제 사용할까?
재귀 함수는 문제가 재귀적으로 정의될 때 특히 적합합니다. 트리 구조 탐색(예: DFS), 분할 정복(퀵 정렬, 병합 정렬), 백트래킹 문제 등에서 직관적이고 간결하게 구현할 수 있습니다.
(위 내용은 추후에 딥다이브 해서 포스팅해 보도록 하겠습니다.)
그러나 호출 깊이가 깊어질 가능성이 있거나 성능 최적화가 중요한 경우 반복문으로 변환하는 것이 좋습니다.
마무리
재귀 함수는 문제를 간결하고 직관적으로 해결하는 강력한 도구입니다. 특히 유클리드 호제법처럼 수학적 정의에 충실한 문제에서는 코드의 가독성을 높이는 데 큰 장점이 있습니다.
다만, 성능이나 메모리 사용이 중요한 경우 반복문으로 구현하는 것도 중요해 보입니다!