[Java] 14. 재귀호출

 

 

 

 

저희는 저번 시간에 메서드에 대해 배웠습니다.
보통은 A 메서드에서 B 메서드를 호출해서 기능을 분리하거나 재사용하곤 했죠.

그렇다면 이런 궁금증이 생길 수 있습니다.

A 메서드가 자기 자신인 A 메서드를 다시 호출할 수 있을까?

 

정답은..

✅ 가능합니다!

 

이렇게 메서드가 자기 자신을 호출하는 방식을 재귀 호출이라고 합니다.

하지만 여기서 주의할 점이 하나 있어요.

 

종료조건이 없다면?

 

A → A → A → A ...
계속해서 끝나지 않고 호출되기 때문에
❗ 프로그램이 무한 루프에 빠지고
❗ 결국 StackOverflowError(스택 오버플로우) 라는 오류가 발생합니다.

그래서 재귀호출에는 반드시 종료 조건이 있어야 합니다.

 

이번 글에서 재귀호출에 대해 더 자세히 알아보겠습니다!

 

 

 

 

---

재귀호출이란?

재귀호출이란 메서드 또는 함수가 자기 자신을 다시 호출하는 것입니다.  큰 문제를 같은 형태의 더 작은 문제로 쪼개며 반복적으로 해결할 수 있을 때 유용합니다.

 

쉽게말하면?

• 내가 나를 다시 호출한다
• 큰 문제 → 더 작고 같은 형태의 문제로 → 반복해서 풀기

 

 

재귀호출의 필요성

• 문제를 더 작게 나눌 수 있을 때 (예: 수학, 알고리즘)
• 트리(Tree), 그래프 탐색처럼 계층적인 구조를 순회할 때
• 반복문보다 더 직관적이고 간결하게 표현하고 싶을 때

 

 

재귀호출의 필요 조건

• 종료조건 : 더 이상 자기 자신을 호출하지 않고 종료하는 조건  - 필수❗
• 재귀조건 : 자기 자신을 다시 호출하는 부분

💡 종료 조건이 없다면 무한 반복 → StackOverflowError 발생!

 

 

실습 예제 - 팩토리얼 계산

팩토리얼이란?

자연수 n에 대해1부터 n까지의 모든 양의 정수를 곱한 값을 의미합니다. 수학 기호로는 n! 로 표현합니다.

• n! = n × (n-1) × (n-2) × ... × 1
• 예: 5! = 5 × 4 × 3 × 2 × 1 = 120

public class FactorialExample {

    public static int factorial(int n) {
        if (n == 1) {                // 종료 조건
            return 1;
        }

        return n * factorial(n - 1); // 재귀 호출
    }

    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("5! = " + result);
    }
}

 

- 출력 결과 -

5! = 120

 

프로그램 실행 흐름은 아래와 같습니다.

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

 

 

실습 예제 - 피보나치 수열

피보나치 수열이란?

피보나치 수열은 앞의 두 항을 더해서 다음 항을 만드는 수열입니다.

• f(n) = f(n-1) + f(n-2)...
• n    :  0   1   2   3   4   5   6   7   8   9...
• 값 f(n):  0   1   1   2   3   5   8  13  21  34...

public class FibonacciExample {

    public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 9; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

- 출력 결과 -

0 1 1 2 3 5 8 13 21 34

 

프로그램 실행 흐름은 아래와 같습니다.

fib(5)
= fib(4) + fib(3)
= (fib(3) + fib(2)) + (fib(2) + fib(1))
= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
= (((1 + 1) + (1 + 0)) + ((1 + 0) + 1))
= ((2 + 1) + (1 + 1))
= (3 + 2)
= 5

 

 

재귀 호출 주의 사항

1. 종료 조건이 필수
    ➡ 종료 조건이 없으면 무한 호출로 인해 프로그램 오류 발생
2. 호출 깊이 주의
    ➡ 너무 깊은 재귀는 StackOverflowError 발생 가능
3. 호출 깊이가 깊을 경우 반복문 전환 고려
    ➡ 단순 루프라면 반복문이 더 빠르고 안정적

 

재귀 호출은 함수 호출 시마다 스택 메모리에 쌓이는 구조이기 때문에, 메모리 사용량이 많고 호출 깊이가 깊어질수록 부담이 커집니다. 특히, 재귀가 너무 깊어지면 속도가 느려지거나 StackOverflowError가 발생할 수 있습니다. 따라서 재귀 호출이 너무 깊어질 경우, 반복문으로 전환하는 것이 성능과 안정성 측면에서 더 유리합니다

 

 

재귀 호출 vs 반복문 비교

 

 

요약하자면..

재귀 호출은 구조가 간결하고, 가독성이 좋을 수 있지만, 스택을 많이 사용하고 성능이 떨어질 수 있습니다.

반복문은 일반적으로 더 빠르고 안정적이며, 메모리 사용도 적지만, 가독성이 떨어질 수 있습니다.

 

 

 

 

읽어주셔서 감사합니다 😊

 

---

소스 코드 바로가기