Java 재귀 이해: 동작 원리, 예제, 장단점 분석

Java 재귀

이 가이드는 Java 재귀 메서드를 설명하고, 고전적인 팩토리얼 예제를 통해 동작을 살펴보며 재귀 사용의 장단점을 평가합니다.

Java에서 자기 자신을 호출하는 메서드를 재귀 메서드라 하며, 이 기법을 재귀라고 합니다. 간단한 실생활 예로는 두 거울이 마주 보는 경우가 있습니다: 각 반영은 또 다른 거울 상이 되어 빛이 흡수될 때까지 반복됩니다.

---

재귀 동작 원리

위 그림에서 recurse() 메서드는 main()에서 호출됩니다(일반 호출). recurse() 내부에서 같은 메서드가 자신을 다시 호출하여 재귀 호출을 만듭니다. 무한 루프를 방지하려면 각 재귀 호출에 종료 조건이 있어야 하며, 일반적으로 if…else 문으로 구현합니다.

---

예제: 재귀를 이용한 팩토리얼 계산

class Factorial { static int factorial(int n) { if (n != 0) // 종료 조건 return n * factorial(n - 1); // 재귀 호출 else return 1; } public static void main(String[] args) { int number = 4, result; result = factorial(number); System.out.println(number + " factorial = " + result); } }

출력:

4 factorial = 24

factorial() 메서드는 main()에서 인수 number와 함께 호출됩니다. factorial() 내부에서

return n * factorial(n-1);

줄이 메서드를 감소된 값으로 자기 호출하게 합니다. n = 4로 시작하여 호출이 진행됩니다: 4 → 3 → 2 → 1 → 0. n이 0에 도달하면 if 조건이 실패하여 1을 반환합니다. 누적된 곱이 콜 스택을 통해 main()으로 다시 전파됩니다.

---

팩토리얼 프로그램 실행 흐름

아래 이미지는 실행 중 콜 스택의 변화를 보여줍니다.

---

재귀의 장단점

• 장점: 재귀 패턴에 자연스럽게 맞는 문제(트리 순회, 조합 생성 등)에 대해 코드를 단순화합니다. 종종 더 짧고 읽기 쉬운 구현이 됩니다.
• 단점: 각 재귀 호출이 스택 공간을 소비하므로 깊은 재귀는 스택 오버플로를 유발할 수 있습니다. 재귀 솔루션은 일반적으로 반복 솔루션보다 메모리 효율이 낮고 느릴 수 있습니다.

전반적으로 재귀는 높은 메모리 사용량과 잠재적 성능 오버헤드 비용으로 우아한 솔루션을 제공합니다. 깊이 제한이 있는 많은 사용 사례에서 이 트레이드오프는 가치가 있습니다.

추천 읽기: 재귀의 장단점은 무엇인가?