재귀

재귀 (Recursion)

재귀는 복잡한 문제를 동일한 형태의 더 작은 문제로 나눠서 해결하는 기법
함수 내부에서 자기 자신을 호출하여 점진적으로 문제를 해결해 나간다.

재귀의 기본 구조

1. 기저 조건 (Base Case)
   • 재귀 호출을 중단하기 위한 종료 조건
   • 없을 경우 무한 호출로 이어질 수 있음
2. 재귀 호출 (Recursive Call)
   • 문제를 더 작은 형태로 분할하고 자신을 다시 호출

예제 1: 팩토리얼

public static int factorial(int n) {
    if (n == 1) return 1;          // Base Case
    return n * factorial(n - 1);   // Recursive Call
}

실행 흐름 (factorial(4))

factorial(4)
→ 4 * factorial(3)
→ 4 * 3 * factorial(2)
→ 4 * 3 * 2 * factorial(1)
→ 4 * 3 * 2 * 1 = 24

 

예제 2: 피보나치 수열

public static int fibo(int n) {
    if (n == 1 || n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

실행 흐름 (fibo(5))

fibo(5)
→ fibo(4) + fibo(3)
→ (fibo(3) + fibo(2)) + (fibo(2) + fibo(1))
→ ...
→ 결과: 5

 

재귀의 시간 복잡도

재귀 시간 복잡도 = 재귀 호출 수 × 호출 당 연산 시간

함수	호출 횟수	시간 복잡도
factorial(n)	n	O(n)
fibo(n)	2ⁿ (중복 호출)	O(2ⁿ)

무한 재귀 방지: 종료 조건과 제어 조건

재귀는 종료 조건이 없다면 무한히 반복될 수 있으므로, 다음과 같은 방식으로 제어해야 합니다.

public static void dfs(int cur) {
    visited[cur] = true;
    for (int next : graph.get(cur)) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

• if (!visited[next]) → 재귀 호출을 제한하는 필터 역할
• 명시적 종료 조건은 아니지만, 무한 순환 방지 기능 수행

재귀 사용 시 유의사항

1. 종료 조건을 반드시 설정할 것
   • 종료 조건이 없으면 StackOverflowError 발생 가능
2. 재귀 깊이에 주의할 것
   • 자바에서의 기본 호출 스택 깊이는 약 10,000
   • 그 이상 반복될 수 있는 경우, 반복문으로 대체 고려
3. 불필요한 재귀는 피할 것
   • 반복문으로 해결할 수 있는 문제는 재귀보다 효율적임

재귀와 반복의 선택 기준

상황	추천 방식
트리, 그래프 탐색	재귀 (DFS 등)
단순 반복 처리	반복문
중복 계산이 많은 경우	반복문 + DP

재귀가 많이 사용되는 알고리즘

• 완전탐색 (Brute-force)
• 분할 정복 (Divide and Conquer)
• DFS / 백트래킹
• 트리 순회 (Preorder, Inorder, Postorder)
• 동적 계획법 (Memoization 방식)