[ 알고리즘 ] 재귀(Recursion)

• 재귀 : 큰 문제를 해결하기 위해 동일한 유형의 더 작은 문제로 나누는 방식
• 재귀함수 : 자기 자신을 호출하여 반복적으로 더 작은 문제를 해결하고 결과적으로 원래 문제를 해결해 감
• 완전탐색, 동적계획법(DP), 그래프 탐색(DFS), .트리 순회와 같은 문제에 활용됨

 

구성 요소

1. Base Case(기저 조건)
   • 더 이상 문제를 쪼갤 수 없거나, 답이 명확해지는 종료조건
   • Base Case 가 없으면 재귀는 무한히 호출됨 → RecursionError 발생
2. Recursive Call(재귀 호출)
   • 문제를 더 작은 문제로 나누고 이를 해결하기 위해 자기 자신을 호출함

 

1. factorial

• $1 \text{\textasciitilde} n$ 까지의 정수를 곱한 값

public static int factorial(int n) {
    if (n == 1) { // Base Case
        return 1;
    }
    return n * factorial(n - 1); // Recursive Call
}

• 재귀 함수 호출 수 : $n$
• 재귀 함수 하나 당 시간 복잡도 : $O(1)$
• 재귀의 시간 복잡도 : $O(n * 1)$

 

2. fibonacci

• 피보나치 수열 : 앞 두항의 합이 다음 항이 되는 수열
• 예: $1, 1, 2, 3, 5, 8, 1 3, 21, ...$
• 점화식 : $f(n)=f(n-1)+f(n-2)$
• base case : $f(1)=1, f(2)=1$

 public static int fibo(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

• 재귀함수 호출 수 : $2^n$
• 재귀함수 하나당 시간 복잡도 : $O(1)$
• 재귀의 시간 복잡도 : $O(2^n * 1)$

 

---

 

유의사항

1️⃣ 무한 루프 주의

• 기저 조건이 없으면 무한 루프에 빠질 수 있으므로, 문제를 종료할 조건을 명확히 정의
• 기저 조건이 명확하지 않더라도 조건문을 통해 종료하도록 보장해야 함

2️⃣ 제한을 너무 크게 설정하지 말것

• 재귀 깊이를 크게 설정하면 메모리 초과(Out of Memory)가 발생 가능
• 대부분 10,000 정도면 충분

3️⃣ 대안이 있는 지 고려

• 입력 크기가 재귀 제한을 초과하면, 다른 풀이 시도가 좋음
• 반복문을 사용할 수 있다면, 재귀를 대신해 반복문을 사용하는 것이 더 안전하고 효율적