Java 재귀 호출 (Recursion)
요약
Java 재귀 호출(Recursion)의 개념과 동작 원리를 알아봅니다. 기저 조건, 호출 추적, 두 번 호출하는 다중 재귀, boolean[] 방문 체크 등 정보처리기사 실기에 출제되는 Java 재귀 패턴을 정리합니다.
재귀 호출 핵심 정리
메서드와 조건문을 먼저 알고 오면 이해가 쉽습니다. 아래는 이 페이지에서 배울 내용을 미리 정리한 표입니다.
| 개념 | 설명 | 예시 |
|---|---|---|
| 재귀 호출 | 메서드가 자기 자신을 다시 호출 | return fn(n - 1) |
| 기저 조건 | 재귀 호출을 멈추는 조건 | if (n <= 1) return n; |
| 다중 재귀 | 한 번에 자기 자신을 두 번 이상 호출 | fn(n - 1) + fn(n - 2) |
| 방문 체크 | boolean[]로 본 것을 표시하며 재귀 | if (!seen[v]) ... |
아래에서 하나씩 설명합니다.
재귀 호출이란? 쌩기초
재귀 호출(Recursion) 은 메서드가 자기 자신을 다시 호출하는 것입니다.
위 코드에서 fn 메서드 안에서 다시 fn(n - 1)을 호출합니다. 이것이 재귀입니다.
static은 지금은 '이렇게 시작한다' 정도로 넘어가도 됩니다. 메서드 페이지에서 자세히 다룹니다.
재귀 호출 추적하기 기초
재귀 호출은 작은 값부터 먼저 계산하면 쉽게 풀 수 있습니다. 1부터 n까지 모두 곱하는 메서드로 추적해 보겠습니다. 5 x 4 x 3 x 2 x 1 = 120을 구하는 예제입니다.
fn(5)를 호출하면 다음과 같이 동작합니다.
펼쳐 내려가기 (기저 조건에 도달할 때까지)
거꾸로 계산하기 (기저 조건에서부터 역순으로)
| 호출 | 계산 | 반환값 |
|---|---|---|
fn(1) | 기저 조건 (n <= 1) | 1 |
fn(2) | 2 * fn(1) = 2 * 1 | 2 |
fn(3) | 3 * fn(2) = 3 * 2 | 6 |
fn(4) | 4 * fn(3) = 4 * 6 | 24 |
fn(5) | 5 * fn(4) = 5 * 24 | 120 |
출력: 120
자기 자신을 두 번 호출하는 재귀 기초
재귀 호출이 한 번이 아니라 두 번 이상 있는 경우, 각 호출의 반환값을 모두 구해서 합쳐야 합니다.
이 메서드는 fn(n - 1)과 fn(n - 2) 두 개의 재귀 호출을 합니다. 이름은 앞 섹션과 같은 fn이지만 별개의 새 메서드입니다.
fn(4) 호출 추적
fn(4)부터 펼쳐 내려갑니다. 각 호출을 fn(n - 1) + fn(n - 2)로 분해하고, 기저 조건(n <= 1)에 도달하면 멈춥니다.
같은 값이 여러 번 등장하지만, 입력이 같으면 몇 번 불러도 답이 같으므로 한 번만 계산하면 충분합니다. 가장 작은 값부터 거꾸로 계산합니다.
| 호출 | 계산 | 결과 |
|---|---|---|
fn(0) | 기저 조건 (n <= 1) | 0 |
fn(1) | 기저 조건 (n <= 1) | 1 |
fn(2) | fn(1) + fn(0) = 1 + 0 | 1 |
fn(3) | fn(2) + fn(1) = 1 + 1 | 2 |
fn(4) | fn(3) + fn(2) = 2 + 1 | 3 |
fn(4)의 출력: 3
다중 재귀는 한쪽 호출만 따라가다 보면 다른 쪽을 빠뜨리기 쉽습니다. 두 호출을 모두 추적해야 합니다.
구간을 나눠 호출하는 재귀 심화
다중 재귀는 같은 값(n)이 아니라 배열의 구간을 나눠 호출하기도 합니다. 두 가지 도구가 자주 쓰입니다.
- 시작 인덱스(start)와 끝 인덱스(end) 사이의 가운데:
mid = (start + end) / 2— 정수끼리 나누므로 소수점 아래는 버립니다. 예:(0 + 3) / 2 = 1 - 두 값 중 큰 쪽:
Math.max(x, y)— 예:Math.max(3, 7) = 7
이 메서드는 앞 섹션과 이름이 다른 새 메서드입니다.
구간을 mid 기준으로 왼쪽·오른쪽으로 나눠 양쪽을 재귀 호출한 뒤, 두 결과 중 큰 쪽(Math.max)에 가운데 값 a[mid]를 더해 위로 올립니다. 더 나눌 수 없는 지점(start >= end)에 도달하면 0을 반환하고, 값은 부모 갈림길에서 a[mid]로 더해집니다.
배열 {1, 3, 2}(인덱스 0 ~ 2)로 divide(a, 0, 2)를 호출해 추적해 봅니다.
펼쳐 내려가기
거꾸로 계산하기
25년1회 실기 기출이 이 분할 방식을 사용합니다. 아래 기출 문제에서 직접 확인해 보세요.
재귀로 배열 방문 표시하기 심화
재귀 호출이 끝나고 돌아오는 길에 boolean[] 배열로 이미 본 값을 표시하면, 배열을 훑으며 중복을 걸러낼 수 있습니다. boolean은 참(true)과 거짓(false) 두 값만 갖는 자료형이라, 본 값은 true로 켜 두고 다시 만나면 건너뛰는 표시로 쓰기 좋습니다. 끝에서부터 호출을 펼친 뒤, 앞에서부터 거꾸로 올라오며 결과를 조립하는 방식입니다.
아래는 정수 배열에서 처음 보는 숫자만 남기는 예제입니다.
이 메서드도 이름은 fn이지만 앞 섹션과 완전히 다른 새 메서드입니다.
핵심은 재귀 호출이 if 검사보다 먼저 실행된다는 점입니다. fn이 자기 자신을 끝까지(i < 0) 호출한 뒤, 거꾸로 돌아오면서 seen[v]를 확인합니다.
- 재귀가
i를 1씩 줄이며 끝까지 내려가 멈춘 뒤, 가장 깊은 호출인 첫 원소(인덱스 0)부터seen검사가 시작되어 마지막 원소 방향으로 올라옵니다. !seen[v]에서!는 참/거짓을 뒤집는 기호입니다.seen[v]가false(아직 못 봄)일 때!false = true가 되어if가 실행됩니다. 표시한 뒤v + result로 숫자를 앞에 붙이는데, Java에서 정수와 문자열을+로 연결하면 계산이 아니라 글자로 이어 붙입니다(3 + "13" = "313"꼴). 새 숫자를 앞에 붙이므로 결과는 첫 등장 순서의 역순이 됩니다. 최종적으로 "213"이 출력되는 핵심 원리입니다.- 이미 본 숫자면
result를 그대로 넘겨 중복을 건너뜁니다.
여기서 seen은 위치가 아니라 값 자체를 인덱스로 씁니다(seen[v]). 그래서 등장할 수 있는 값보다 크게 잡아야 합니다. 아래 예제는 작은 숫자만 나오므로 넉넉하면 되고, 24년2회 기출은 글자를 인덱스로 쓰려고 256칸(new boolean[256])을 잡습니다.
직접 추적하기
배열이 int[] a = {3, 1, 3, 2, 1} 이고 seen은 처음엔 모두 false라고 하겠습니다. fn(a, 4, seen)을 호출하면 인덱스 4부터 -1까지 펼쳐 내려간 뒤, 거꾸로 올라오며 검사합니다.
펼쳐 내려가기
거꾸로 올라오며 검사
| 호출 | a[i] | seen 검사 | 반환값 |
|---|---|---|---|
fn(a, 0) | 3 | 처음 → 표시 | 3 |
fn(a, 1) | 1 | 처음 → 표시 | 13 |
fn(a, 2) | 3 | 이미 봄 → 건너뜀 | 13 |
fn(a, 3) | 2 | 처음 → 표시 | 213 |
fn(a, 4) | 1 | 이미 봄 → 건너뜀 | 213 |
출력: 213 — 처음 등장한 숫자(3, 1, 2)만 남고, 새 숫자를 앞에 붙였기 때문에 등장 순서의 역순이 됩니다.
같은 패턴이 문자열에도 그대로 적용됩니다. 24년2회 실기 기출은 문자열의 각 글자를 seen으로 검사해 중복을 걸러냅니다. 아래 기출 문제에서 호출이 펼쳐지고 돌아오는 과정을 직접 추적해 보세요.
실기 문제 풀이 전략 심화
재귀 문제 풀이 순서
- 기저 조건 확인: 조건문(
if)에서 어떤 값을 반환하고 멈추는지 확인 - 재귀 호출 파악:
return문에서 자기 자신을 어떻게(몇 번) 호출하는지 확인 - 호출 펼치기: 기저 조건에 도달할 때까지 호출을 위에서 아래로 펼치기
- 역순 계산: 기저 조건의 반환값부터 거꾸로 올라오며 계산