재귀 호출(Recursive Call) 개념

2025-03-30 2 분 소요

재귀 호출(Recursive Call)은 메서드가 자기 자신을 다시 호출하면서 문제를 작은 하위 문제로 분할해 해결하는 기법입니다. 제대로 된 종료 조건(base case)이 없으면 무한 루프와 StackOverflowError가 발생하므로, 중단 조건은 필수입니다.

재귀 호출의 핵심 특징

1. 종료 조건(Base Case)

재귀를 멈출 타이밍을 명시해야 스택 오버플로우를 방지합니다.

2. 스택 프레임 사용

호출마다 새 스택 프레임이 생성·소멸되어 메모리 사용량이 늘어납니다.

3. 간결·직관

복잡한 로직을 분할 정복으로 표현해 코드가 짧고 이해하기 쉽습니다.

필수 예제 3선

1. 합계 구하기

int recursiveSum(int n){
    if (n == 1) return 1;          // 종료 조건
    return n + recursiveSum(n - 1); // 재귀 호출
}

동작: n + (n-1) + … + 1

2. 팩토리얼

int factorial(int n){
    if (n == 1) return 1;          // 종료 조건
    return n * factorial(n - 1);   // 재귀 호출
}

결과: n! = n × (n-1)!

3. 하노이의 탑

void hanoi(int n, char from, char to, char aux){
    if (n == 1){
        System.out.printf("Move 1 from %c to %c%n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);           // Step 1
    System.out.printf("Move %d from %c to %c%n", n, from, to); // Step 2
    hanoi(n - 1, aux, to, from);           // Step 3
}

세 단계로 디스크 n개를 옮깁니다.

반복문 vs. 재귀 호출

구분	재귀 호출	반복문
코드 길이	짧고 직관적	길어질 수 있음
성능	스택 사용 → 느릴 수 있음	일반적으로 빠름
메모리	스택 프레임당 메모리 소모	적음
적합한 문제	트리 탐색, 분할 정복	단순 반복 계산

재귀 호출 최적화 방법

● 메모이제이션(Memoization)

이미 계산한 값을 캐싱하여 중복 호출을 제거합니다.

int[] memo = new int[1000];
int fib(int n){
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

● 꼬리 재귀(Tail Recursion)

재귀 호출이 마지막 작업일 때 반복문으로 최적화될 수 있어 성능이 향상됩니다.

사용 시 주의사항

종료 조건은 반드시 명확히 작성한다.
호출 깊이가 크면 StackOverflowError 가능 → 반복문 전환 고려.
성능이 중요한 경우 메모이제이션·꼬리 재귀 또는 반복문 대체를 검토.

결론

재귀 호출은 복잡한 알고리즘을 간결하고 논리적으로 표현하는 강력한 도구입니다. 하지만 스택 메모리 한계와 성능 저하를 유발할 수 있으므로, 종료 조건·최적화 기법을 반드시 함께 고려해야 합니다.

질문 정리

재귀 호출이 반복문보다 항상 느린가요?

스택 프레임 생성 비용 때문에 일반적으로 느리지만, 메모이제이션이나 꼬리 재귀 최적화로 일부 개선할 수 있습니다.
JVM이 꼬리 재귀를 자동 최적화하나요?

표준 HotSpot JVM은 기본적으로 꼬리 재귀 제거를 수행하지 않습니다. 반복문으로 변환하는 편이 안전합니다.
StackOverflowError를 방지하려면?

종료 조건을 확실히 명시하고, 필요하면 재귀 깊이를 제한하거나 반복문으로 리팩터링하세요.
피보나치 수열은 재귀가 비효율적인가요?

순수 재귀는 중복 호출이 많아 O(2ⁿ) 이지만, 메모이제이션이나 DP를 사용하면 O(n) 으로 최적화됩니다.
재귀 호출 디버깅 팁이 있나요?

로그에 재귀 깊이를 함께 출력하거나, 디버거의 스택 프레임 기능을 활용하면 흐름을 쉽게 추적할 수 있습니다.

X Facebook LinkedIn Bluesky