(코테) [Java] 재귀

재귀란?

함수가 자기 자신을 다시 호출하는 프로그래밍 기법

복잡한 문제를 같은 구조의 더 작은 문제로 나눠서 푸는 방식이며

종료 조건을 통해 반복을 마무리함으로써 최종 결과를 만들어내는 방법

DFS할 때 사용 많이 했었음!

재귀 함수의 구조

void recursive() {
    // 1. 종료 조건 (Base Case)
    if (조건) return;

    // 2. 재귀 호출 (작은 문제로 분할)
    recursive();
}

예제 1: 1부터 N까지 출력

public class Main {
    public static void printNumbers(int n) {
        if (n == 0) return;         // 종료 조건
        printNumbers(n - 1);        // n-1 먼저 출력
        System.out.println(n);      // 호출이 끝나고 나서 출력됨 (후위)
    }

    public static void main(String[] args) {
        printNumbers(5);  // 1 2 3 4 5
    }
}

📌 재귀는 "쌓였다가 다시 돌아가는 구조"이기 때문에 출력 순서가 직관적이지 않을 수 있음

→ 그래서 처음에 문제 풀 때 손으로 써가면서 이해하면 조금 더 잘 된 느낌이였음!

예제 2: 팩토리얼

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

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 출력: 120
    }
}

재귀의 작동 원리: 콜 스택(Call Stack)

재귀 함수는 자기 자신을 계속 호출하면서 스택에 쌓이고

Base Case(종료 조건)에 도달한 뒤부터 스택이 하나씩 풀리며 계산됨

factorial(3)
= 3 * factorial(2)
= 3 * 2 * factorial(1)
= 3 * 2 * 1 * factorial(0)
= 3 * 2 * 1 * 1
= 6

재귀에서 주의할 점

항목 설명

종료 조건 필수	없으면 StackOverflowError 발생
너무 깊은 호출 X	자바는 재귀 호출이 너무 깊으면 스택이 터짐 (약 1만 번 이상)
반복문으로 대체 가능	재귀는 코드가 간단해지지만, 속도나 메모리는 반복문이 더 효율적일 수 있음

반복문 vs 재귀 비교

// 재귀 방식
void countdown(int n) {
    if (n == 0) return;
    System.out.println(n);
    countdown(n - 1);
}

// 반복문 방식
void countdownLoop(int n) {
    while (n > 0) {
        System.out.println(n);
        n--;
    }
}

📌 대부분의 재귀는 반복문으로도 변환이 가능함!

하지만 문제 구조가 계층적이거나 트리 탐색처럼 분기되는 경우엔 재귀가 더 직관적임

예를 들어 노드를 타고 내려가면서 모든 경우를 탐색해야 하는 문제에서는

재귀를 활용해 깊이 우선 탐색(DFS) 방식으로 모든 경로를 시도 해볼 수 있음

 

코테 풀면서 많이 봤던

1. 재귀를 할 때 범위를 줄여나갈 때 좌표도 같이 줄여나가서 각 구역마다 해결

2. 종료 조건을 잘 걸어서 빠르게 빠져나가게 해서 시간초과 막기

 

등등.. 많이 문제를 풀어보면 더 다양한 방식들이 있다는 것을 매번 느끼는 중 ㅠ

마무리

• 재귀는 문제를 작게 나누는 사고 훈련에 매우 효과적!
• 항상 종료 조건(Base Case)을 명확히 확인 할 것! → 그래야지 종료가 잘됨 아니면 계속 재귀하거나 시간 초과 발생하는 경우 O