[알고리즘] 재귀 (Recursion)

재귀에 대해 공부 후 정리하였습니다.

Summary

• 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법
• 종료 조건(기저 조건)이 반드시 필요하며, 함수 호출 스택을 사용
• 문제에 따라 다르지만 보통 O(분기^깊이)
• 분할정복, 백트래킹, DFS/BFS, 수학적 정의(팩토리얼, 피보나치 등) 등에 많이 사용

수학적 귀납법

public static void func(int n) {
    if (n == 0) return;
    System.out.println(n);
    func(n - 1);
}

• 절차지향적 사고(코드가 동작하는 순서대로 생각)를 버려야 재귀를 이해할 수 있음
• 귀납적 사고
  • func(1)이 1을 출력한다.
  • func(k)가 k k-1 k-2 … 1을 출력하면 func(k+1)은 k+1 k k-1 k-2 … 1을 출력한다.
    (k+1 출력 후 func(k)을 호출하기 때문)
  • 두 문장이 참이므로 귀납적으로 func()이 n~1까지 차례로 출력하는 함수임을 알 수 있음

1️⃣ 개념

재귀는 함수가 자기 자신을 직접 혹은 간접적으로 호출하는 프로그래밍 기법이다.
복잡한 문제를 동일한 형태의 더 작은 문제로 나누어 해결한다.

2️⃣ 특징

• 기저 조건(Base Case): 무한 호출을 막기 위해 종료 조건 반드시 필요
• 스택(Stack) 메모리를 사용하여 함수 호출을 저장
• 모든 재귀 함수는 반복문만으로 동일한 동작하는 함수 만들 수 있음
• 재귀는 반복문 구현에 비해 코드가 간결하나, 메모리/시간에서는 손해임
• 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음 (동일한 계산을 여러번 반복)

3️⃣ 시간 복잡도

재귀 함수의 시간 복잡도는 호출 횟수 × 각 호출의 처리 시간으로 계산됨

• 피보나치 수열 단순 재귀 → O(2^N)
• 팩토리얼, DFS → O(N)
• 분할 정복(이분 탐색, 병합 정렬) → O(N log N)

4️⃣ 구현 방법 (ex. 하노이 탑)

• 함수의 인자로 어떤 것을 받고 어디까지 계산 후 자신에게 넘겨줄지 명확하게 정해야 함
• 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함
• 모든 입력은 기저 조건으로 수렴해야 함

1. 함수의 정의
   • void func(int a, int b, int n) : 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수
2. 기저 조건 정의 (Base Case) - 지극히 자명한, 계산 없이도 바로 결과를 알 수 있는 경우로 설정
   • n = 1일 때, a에서 b로 옮기도록 하기
3. 재귀식 작성
   • 기둥 번호의 합이 6이므로, a or b가 아닌 번호는 6-a-b번임
   • n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다. => func(a, 6-a-b, n-1)
   • n번 원판을 기둥 a에서 기둥 b로 옮긴다. => a b 출력
   • n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다. => func(6-a-b, b, n-1)

5️⃣ 예시 코드

팩토리얼

public class RecursionExample {
    // 팩토리얼: n! = n * (n-1)!
    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
    }
}

피보나치 수열

public class RecursionExample {
    // 피보나치: F(n) = F(n-1) + F(n-2)
    public static int fibonacci(int n) {
        if (n == 0) return 0;   // 기저 조건
        if (n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 호출
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(6)); // 출력: 8
    }
}

6️⃣ 자주 사용하는 곳

• 수학적 정의: 팩토리얼, 피보나치, 최대공약수(GCD)
• 탐색 알고리즘: DFS(깊이 우선 탐색), 백트래킹(순열/조합/부분집합)
• 분할 정복: 병합 정렬, 퀵 정렬, 이분 탐색
• 트리/그래프 탐색: 트리 순회(전위/중위/후위), 그래프 탐색