▶ Java Methods

자바 재귀 함수: 기본 개념과 예제

재귀(Recursion)는 자바 프로그래밍에서 복잡한 문제를 더 간단하게 해결할 수 있도록 도와주는 중요한 개념입니다. 재귀는 메서드가 자기 자신을 호출함으로써 반복적인 작업을 수행하는 방식으로, 특히 트리 탐색, 팩토리얼 계산, 검색 알고리즘 등과 같은 문제에서 유용하게 사용됩니다. 이 글에서는 재귀의 기본 개념과 자바에서 이를 구현하는 방법을 살펴보고, 이해를 돕기 위한 예제도 함께 제공합니다.

자바에서 재귀란?

자바에서 재귀는 메서드가 문제를 해결하기 위해 자기 자신을 호출하는 프로세스를 의미합니다. 모든 재귀적인 해결 방법에는 두 가지 중요한 요소가 있습니다:

기저 사례(Base Case): 재귀 호출을 멈추는 조건입니다. 기저 사례가 없으면 재귀는 무한히 계속되어 StackOverflowError가 발생할 수 있습니다.
재귀 사례(Recursive Case): 문제를 더 작은 단위로 나누고, 그 단위를 해결하기 위해 다시 메서드를 호출하는 부분입니다.

자바 재귀 함수 구조

다음은 재귀 함수의 기본 구조입니다:

public class RecursionExample {
    public static int recursiveMethod(int n) {
        // 기저 사례: n이 0이면 재귀 종료
        if (n == 0) {
            return 1;
        }
        // 재귀 사례: n을 줄여가며 함수 호출
        return n * recursiveMethod(n - 1);
    }

    public static void main(String[] args) {
        int result = recursiveMethod(5);
        System.out.println("결과: " + result); // 출력: 결과: 120
    }
}

재귀 함수의 동작 원리

위 코드에서 recursiveMethod는 팩토리얼을 계산하는 재귀 함수입니다. 팩토리얼(factorial)은 수학적으로 5! = 5 * 4 * 3 * 2 * 1 과 같은 형태로 표현되며, 이는 재귀적인 문제로 간주할 수 있습니다.

기저 사례: n == 0일 때, 함수는 1을 반환하여 재귀 호출을 멈춥니다.
재귀 사례: n이 0보다 클 때, 함수는 n * recursiveMethod(n - 1)을 호출하여 n을 점차 줄여나갑니다.

재귀의 장점

코드 단순화: 복잡한 반복문을 사용하지 않고도 간단한 방식으로 문제를 해결할 수 있습니다.
문제 분할: 문제를 더 작은 문제로 분할하여 해결할 수 있습니다.

재귀의 단점

성능 저하: 재귀 호출이 반복되면 메서드 호출 스택이 쌓여 많은 메모리를 소모할 수 있습니다.
디버깅 어려움: 복잡한 재귀는 디버깅이 까다로울 수 있습니다.

자주 사용되는 재귀 예제

1. 팩토리얼 계산

public class Factorial {
    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
    }
}

2. 피보나치 수열 계산

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

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

3. 배열의 합 구하기

public class ArraySum {
    public static int arraySum(int[] arr, int n) {
        if (n <= 0) {
            return 0;
        }
        return arr[n - 1] + arraySum(arr, n - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(arraySum(arr, arr.length)); // 출력: 15
    }
}

재귀 함수 사용 시 주의 사항

기저 사례 정의: 모든 재귀 함수에는 반드시 재귀를 멈추는 기저 사례가 있어야 합니다. 그렇지 않으면 함수는 무한히 호출되어 오류가 발생할 수 있습니다.
스택 오버플로우 주의: 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있으므로, 필요한 경우 반복문으로 해결하는 방법도 고려해야 합니다.

요약

재귀는 문제를 간결하게 해결할 수 있는 강력한 도구이지만, 적절한 사용이 중요합니다. 기저 사례와 재귀 사례를 잘 정의하고, 문제를 작은 단위로 분할하는 방식으로 문제를 해결하는 것이 핵심입니다. 또한 재귀를 사용할 때는 성능과 메모리 사용량에 유의해야 하며, 필요에 따라 반복문을 사용하는 방법도 고려해야 합니다.

코딩 스쿨 Java

Java Recursion