재귀

재귀는 큰 문제를 해결하기 위해 동일한 유형의 더 작은 문제로 나누는 방식

자기 자신을 호출하여 반복적으로 작은 문제를 해결해 나가며, 궁극적으로 원래 문제를 해결함

📌 완전 탐색, DP, 그래프, 트리 순회와 같은 알고리즘 문제를 푸는 데 중요!

 

구성 요소

1. 기저 조건 (Base Case)
   • 더 이상 문제를 쪼갤 수 없거나, 답이 명확해지는 종료 조건
   • 기저 조건이 없다면, 무한 호출되며 `Recursion Error` 발생
2. 재귀 호출 (Recursive Call)
   • 문제를 더 작은 문제로 나누고, 이를 해결하기 위해 자기 자신 호출

---

시간 복잡도

재귀의 시간복잡도를 구하는 건 어려움. 수학적으로 접근해 엄밀히 구하려면, 실용성이 떨어짐
∴ 대략적으로 계산해야 함

📌 시간 복잡도 =  재귀 함수 호출 수 X 재귀 함수 당 시간 복잡도

예제

팩토리얼 구하기

public static int factorial(int n) {
    if (n == 1) { 
        return 1;
    }
    return n * factorial(n - 1);
}

• 재귀 함수 호출 수 = `N`
• 함수 당 시간 복잡도 = O(1)
• 전체 시간 복잡도  = N X 1 = `O(N)`

---

피보나치 수 구하기

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

• 재귀 함수 호출 수 = `2ⁿ`
• 함수 당 시간 복잡도 = O(1)
• 전체 시간 복잡도  = 2ⁿ X 1 = `O(2ⁿ)`

---

재귀 사용 시 유의사항

1. 종료 조건을 명확히 정의
   • 재귀 함수가 끝나지 않으면 무한 호출로 인해 `StackOverflowError` 발생
   • 탈출 조건이 없거나 잘못 정의돼 있으면 X
   • 인자가 재귀 호출 시에 변해야 함 (매개변수가 변하지 않으면 탈출 조건 못 만남)
2. 제한을 너무 크게 설정 X
   • 재귀의 깊이가 지나치게 깊은 경우 메모리 초과 에러 발생
   • 대부분의 경우 `10,000`정도로 설정하면 충분함
3. 대안 고려
   • 입력 크기가 재귀 제한을 초과하는 경우, 다른 풀이 시도
   • 반복문을 활용할 수 있다면, 재귀 보다 반복문을 선택할 것 (안전 & 효율적)