Java 재귀함수
🔥 매회 출제 (priority 3)
🌱 왜 배우나
러시아 인형 마트료시카를 떠올려 보자. 큰 인형을 열면 안에 같은 모양의 작은 인형이 있고, 또 열면 더 작은 인형이 나온다. 마지막 인형에 이르면 멈춘다. 재귀(recursion)는 이 장면을 코드로 옮긴 것이다. “큰 문제를 같은 모양의 작은 문제로 쪼개다가, 가장 작아지면 멈춘다.” 숫자 1234를 뒤집어 4321로 만드는 일도 그렇다. 끝자리 4를 떼고, 남은 123을 또 같은 방식으로 뒤집으면 된다. 이 구조를 모르면 재귀 문제 앞에서 머릿속이 하얘진다.
📖 핵심 개념
재귀함수(recursive function)는 자기 자신을 다시 부르는 함수다. 함수(function)는 특정 작업을 묶은 코드 덩어리를 말한다.
재귀가 성립하려면 반드시 두 부품이 있어야 한다.
- 종료 조건(base case): “더 이상 쪼갤 수 없을 때 멈추는 규칙.” 마트료시카의 마지막 인형에 해당한다. 코드에서는
if (n <= 0) return;같은 줄이다. - 재귀 단계(recursive step): 문제를 한 단계 작게 만든 뒤 자기 자신을 다시 부르는 부분.
f(n - 1)이나f(n / 10)같은 호출이다.
함수가 자기를 부를 때마다 컴퓨터는 호출 스택(call stack)이라는 메모리 공간에 정보를 한 층씩 쌓는다. 종료 조건을 만나면 쌓였던 층이 역순으로 하나씩 되돌아오면서 결과를 조합한다.
출력 위치가 중요한 포인트다. 재귀 호출 “전”에 출력하면 큰→작은 순방향, “후”에 출력하면 작은→큰 역방향이 된다. 종료 조건이 없으면 스택이 끝없이 쌓여서 StackOverflowError가 난다.
🔍 시각화
┌─────────── f(1234) 호출 흐름 ──────────────┐
│ │
│ f(1234) │
│ ├─ 출력: 1234 % 10 = 4 │
│ └─ f(123) 호출 │
│ ├─ 출력: 123 % 10 = 3 │
│ └─ f(12) 호출 │
│ ├─ 출력: 12 % 10 = 2 │
│ └─ f(1) 호출 │
│ ├─ 출력: 1 % 10 = 1 │
│ └─ f(0) 호출 │
│ └─ 종료 조건: return │
│ │
│ 최종 출력: 4 3 2 1 │
└────────────────────────────────────────────┘
┌─── 출력 위치에 따른 순서 차이 ─────────────┐
│ │
│ 출력 → 재귀호출 (순방향) │
│ print(3), print(2), print(1) → "3 2 1" │
│ │
│ 재귀호출 → 출력 (역방향) │
│ print(1), print(2), print(3) → "1 2 3" │
└────────────────────────────────────────────┘
↔️ 이웃 개념 구분
- 재귀 vs 반복문: 같은 결과를 내지만, 재귀는 함수 자기호출. 반복문(for, while)은 코드 블록을 조건이 참인 동안 돌린다. 재귀는 짧고 의도가 선명한 대신 호출 스택 메모리를 더 쓴다.
- 종료 조건 vs 반복 조건: 재귀의 종료 조건은 “멈출 때”를 정한다. 반복문의 조건은 “계속 돌 때”를 정한다. 방향이 서로 반대다.
- 호출 전 출력 vs 호출 후 출력: 전에 쓰면 순방향. 후에 쓰면 역방향. 이 한 줄 차이로 시험 답이 바뀐다.
🔑 핵심 용어
- 재귀 호출(recursion): 함수가 자기 자신을 다시 부르는 것
- 종료 조건(base case): 재귀를 멈추는 조건.
if (n <= 0) return;등 - 호출 스택(call stack): 함수 호출 정보를 순서대로 쌓아두는 메모리 공간. 재귀마다 한 층씩 쌓임
- 스택 오버플로우(StackOverflowError): 종료 조건 없이 재귀가 무한 반복될 때 스택이 넘쳐서 발생하는 오류
✅ 스스로 가르쳐보기
재귀가 처음인 친구에게 마트료시카 인형 비유를 쓰지 않고 본인만의 새로운 비유로 한 문장 정의를 만들어 보세요. 그 다음
forward(3)과backward(3)이 왜 서로 반대 순서로 찍히는지 이어서 설명해 보세요.
체크포인트:
- 호출 전 출력이 왜 순방향(3,2,1)인지 말할 수 있는가
- 호출 후 출력이 왜 역방향(1,2,3)인지 말할 수 있는가
- 호출 스택이 쌓였다가 되감기는 과정을 그림으로 그릴 수 있는가
- 종료 조건이 빠지면 무슨 오류가 나는지 말할 수 있는가
🎯 기출 포인트
- 2025-1회: Java 재귀 메서드 결과 추적 (답: 20). 종료 조건과 반환값 계산이 핵심
- 2024-2회: 재귀 + 오버라이딩 혼합. 동적 바인딩으로 어느 클래스의 재귀가 호출되는지 판단
- 출제 패턴:
f(n-1)형태의 재귀 호출 후 반환값 조합. 출력 위치(전/후)로 순서 결정- 트레이싱 팁: 매개변수 → 조건 체크 → 재귀 호출 → 반환값 순서로 표 작성