[JAVA] 재귀 함수(Recursive Function)

재귀 함수(Recursive Function)

함수가 자기 자신을 호출하는 것을 말합니다.

이것은 일반적인 반복문과 달리 함수 내에서 자신을 호출하여 문제를 해결하는 방식입니다.

 

재귀 함수 특징

1. 기본 케이스(Base Case): 재귀 함수는 종료 조건을 가지고 있어야 합니다. 이는 함수가 자기 자신을 호출하는 과정을 종료시키기 위한 조건으로, 종료 조건에 도달하면 재귀 호출이 멈추고 함수가 더 이상 호출되지 않습니다.
2. 재귀 케이스(Recursive Case): 재귀 함수는 자기 자신을 호출하여 더 작은 부분 문제를 해결하는 과정을 포함합니다. 이 부분은 종료 조건에 도달하기 전에 반복적으로 실행됩니다.
3. 스택 메모리 사용: 재귀 함수가 호출될 때마다 호출 스택에 호출된 함수의 정보가 저장됩니다. 이는 호출 스택의 크기를 넘어서면 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.

재귀 함수의 예시로는 팩토리얼 계산, 피보나치 수열, 이진 트리 순회 등이 있습니다.

 

팩토리얼을 재귀 함수로 계산하는 예시

public class Main {
    public static void main(String[] args) {
        int n = 5;
        int result = factorial(n);
        System.out.println("Factorial of " + n + " is: " + result);
    }

    public static int factorial(int n) {
        // 종료 조건: n이 1 이하일 때 1을 반환하여 재귀를 멈춘다.
        if (n <= 1) {
            return 1;
        }
        // 재귀 호출: n * factorial(n-1)을 반환한다.
        return n * factorial(n - 1);
    }
}

재귀 함수를 사용하여 숫자의 팩토리얼을 계산합니다. 팩토리얼 함수에서는 종료 조건으로 n이 1 이하일 때 1을 반환하여 재귀를 멈추도록 합니다. 그렇지 않은 경우에는 n * factorial(n-1)을 반환하여 재귀 호출을 수행합니다.

1. 문제 해결의 자연스러운 표현: 일부 문제들은 재귀적인 접근이 자연스럽고 간편합니다. 예를 들어, 이진 트리 순회나 그래프 탐색 등의 문제는 재귀적으로 해결하기가 편리합니다.
2. 코드의 간결성: 재귀 함수는 반복문을 사용하는 것보다 코드를 더 간결하게 만들 수 있습니다. 특히 일정한 패턴을 가지는 문제나 알고리즘에서는 재귀적 접근이 코드를 간결하고 읽기 쉽게 만들어 줍니다.
3. 점화식과 피보나치 수열과 같은 수학적 문제: 몇몇 수학적 문제는 재귀적으로 정의되며, 이러한 경우에는 재귀 함수를 사용하여 문제를 해결하기가 자연스럽습니다. 예를 들어, 피보나치 수열은 다음과 같은 점화식으로 정의됩니다: F(n) = F(n-1) + F(n-2) (단, F(0) = 0, F(1) = 1).
4. 분할 정복(Divide and Conquer) 알고리즘: 분할 정복 알고리즘은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 이때 재귀 함수를 사용하여 부분 문제를 해결하고, 이를 결합하여 전체 문제를 해결할 수 있습니다.
5. 트리 구조와 관련된 문제: 트리 구조는 자연스럽게 재귀적인 성질을 가지고 있습니다. 따라서 트리 구조와 관련된 문제를 해결할 때는 재귀 함수가 유용하게 사용됩니다.

재귀 함수를 사용할 때는 종료 조건을 반드시 설정하여 무한 반복을 방지해야 합니다. 종료 조건이 충분히 명확하고 완전해야 합니다. 종료 조건이 충족되지 않으면 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.