재귀함수 (Recursion)

재귀함수

 

 

1)  재귀함수 란?

함수가 자기 자신을 호출하는 방식의 함수입니다.

대표적으로, 팩토리얼 계산, 피보나치 수열, 하노이 탑, DFS, 백트래킹 등 모든 깊이 탐색 알고리즘의 기반이 됩니다.

 

 

 

2)  재귀함수의 동작원리

재귀 함수는 내부적으로 '스택 구조'를 따릅니다.
즉, 함수가 호출될 때마다 현재 함수는 잠깐 멈추고, 새로운 함수 호출이 먼저 끝날 때까지 기다립니다.
맨 마지막 호출이 종료되면 차례로 다시 돌아옵니다.

 

 

3)  DFS 활용분야

활용 분야	설명
경로 찾기	특정 노드까지의 경로 유무, 경로 목록 찾기
미로 탐색	출구가 있는지 확인하거나 모든 경로 탐색
백트래킹 문제	N-Queen, 순열/조합, 스도쿠 해결 등
트리 탐색	전위/중위/후위 순회 구현
사이클 탐지	그래프 내 순환 여부 확인
위상 정렬	DFS 기반 구현 가능 (방문 완료 시점 기록)
연결 요소 탐색	연결된 노드 그룹 찾기 (Connected Components)

 

 

 

 

3) 재귀함수의 3요소

요소	설명	예시
Base case (종료 조건)	재귀 호출을 멈추는 조건	if (n == 1) return 1;
Recursive case (자기 호출)	자신을 다시 호출하는 부분	factorial(n - 1)
문제 축소	매 호출마다 문제 크기를 줄임	n → n-1 → ...

 

 

 

 

4) 재귀함수의 주의점

1. 반드시 종료 조건이 있어야 함 (없으면 무한 호출 → StackOverflow)
2. 호출 스택이 깊어질수록 메모리 사용량 증가
3. 반복문보다 느릴 수 있음 → DP/메모이제이션으로 최적화 필요

 

 

 

5) 재귀함수의 예시 - 팩토리얼

n! = n * (n-1) * (n-2) * ... * 1

public class Factorial {
    public static int factorial(int n) {
        if (n == 1) return 1;            // 종료 조건 (Base case)
        return n * factorial(n - 1);     // 자기 자신 호출
    }

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

 

// 동작흐름
factorial(5)
→ 5 * factorial(4)
→ 5 * 4 * factorial(3)
→ 5 * 4 * 3 * factorial(2)
→ 5 * 4 * 3 * 2 * factorial(1)
→ 5 * 4 * 3 * 2 * 1 = 120

 

 

 

 

관련문제
https://devwarriorjungi.tistory.com/entry/%EB%B0%B1%EC%A4%80-10870-Java-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98-5

[백준 10870] Java - 피보나치 수 5