재귀 recursion (JAVA)

📍 재귀 알고리즘 이란?

: 함수가 자기 자신을 다시 호출하여 문제를 해결하는 방법이다.
즉, 하향식 방식(top - down) 이다.

1. 재귀 구성

• 기저 조건(Base Case): 재귀 호출을 멈추는 조건이다.
• 재귀 호출(Recursive Call): 함수가 자기 자신을 다시 호출하여 문제를 점점 작게 만든다.

2. 장단점

(1) 장점

• 직관적이다 -> 코드의 가독성 증가한다.
• 변수 사용량 증가한다.

(2) 단점

• 스택 오버 플로우가 발생할 수 있다. <- 발생하지 않게 하기 위해서는 기저 조건 (base case)를 명확하게 확립하는 것이 중요하다.
• 성능 저하한다.

3. 재귀 예시 : 피보나치

public int factorial(int n) {
    if (n <= 1) return 1;  // 기저 조건
    return n * factorial(n - 1);  // 재귀 호출
}

기저 조건이 나타나야 재귀 호출을 멈춘다.

4. 활용

• 분할 정복
• 탐색 알고리즘
• 동적 프로그래밍

등 다양한 곳에서 활용할 수 있다.

5-1. 꼬리 재귀 Tail Recursion

!! JAVA에서는 지원하지 않는다.

: 함수가 자기 자신을 호출할 때, 그 호출이 함수의 마지막 작업으로 이루어지는 재귀이다. 즉, 함수가 자기 자신을 호출한 후 추가적인 작업을 하지 않고 반환한다.

// 일반적인 재귀 (꼬리 재귀가 아님)
public int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);  // 마지막에 곱셈 연산이 있어 꼬리 재귀가 아님
}

// 꼬리 재귀
public int factorialTail(int n, int acc) {
    if (n == 1) return acc;
    return factorialTail(n - 1, n * acc);  // 재귀 호출이 함수의 마지막 작업
}

5-2. 꼬리 재귀 최적화 Tail Recursion Optimization

: 일부 언어에서 사용할 수 있는 방식으로, 재귀 함수의 마지막 호출이 다시 자기 자신을 호출하는 경우 이를 일련의 반복문으로 변환하는 것이다. 이를 통해 스택 공간을 크게 절약하여 함수 호출의 오버헤드를 제거한다.

// 꼬리 재귀를 사용하지 않은 팩토리얼
public int factorial(int n) {
    return factorialTail(n, 1);
}

// 반복문으로 꼬리 재귀 최적화 적용
public int factorialIterative(int n) {
    int result = 1;
    while (n > 1) {
        result *= n;
        n--;
    }
    return result;
}