재귀 호출(recursive call)
재귀 호출이란 메소드 내부에서 해당 메소드가 또다시 호출되는 것을 의미합니다.
자기 자신을 계속해서 호출하므로, 끝없이 반복될 것이기 때문에 메소드 내에 재귀호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.
재귀 호출을 사용하지 않고 1부터 n까지의 합을 구하는 sum() 메소드
int sum(int n) {
int result = 0;
for (int i = 0; i < n; i++) {
result += i;
}
return result;
}위의 예제에서 sum() 메소드는 재귀 호출을 사용하지 않고 만든 메소드입니다.
해당 메소드의 목적을 직관적으로 알 수 없으며, 코드를 해석해야 무슨 목적으로 만든 메소드인지 알 수 있다는 단점이 있습니다. 즉, 변수 i와 result는 왜 정의되었으며, for문은 왜 사용되었는지 바로 알기 어려운 형태입니다.
재귀 호출을 사용하여 1부터 n까지의 합을 구하는 recursive() 메소드
- 알고리즘 생각해보기
1부터 4까지의 합을 구하는 알고리즘 만든다면?
1부터 4까지의 합은 1부터 3까지의 합에 4를 더하면 된다.
1부터 3까지의 합은 1부터 2까지의 합에 3을 더하면 된다.
1부터 2까지의 합은 1부터 1까지의 합에 2를 더하면 된다.
1부터 1까지의 합은 그냥 1이다. - 의사코드(pseudo code) 작성하기
시작
1. n이 1이 아니면, 1부터 (n-1)까지의 합에 n을 더한 값을 반환
2. n이 1이면, 그냥 1을 반환
끝- 코드로 옮기기
int recursiveSum(int n) {
if (n == 1) {
return 1;
}
return n + recursiveSum(n-1);
}위의 예제에서 탈출조건 없이 재귀함수를 호출하면 스택 영역에서 어떤 일이 일어날까요?
실행 직후 스택 오버플로우(stack overflow)에 의해 종료될 것입니다.
따라서 if문처럼 재귀 호출을 중단하기 위한 조건문을 반드시 포함해야 합니다.
왜 탈출조건이 없다면 스택 오버플로우가 발생하는 걸까요?
먼저 메소드 호출과 스택 영역의 관계를 이해해야 합니다.
- 스택은 후입선출 방식 임을 기억하기!
스택(stack) 영역
메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역입니다.
스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다.
이렇게 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다.
메모리 할당 및 관리의 관점에서 힙과 스택 영역의 동작 방식
힙 영역에 데이터가 할당될수록 위 -> 아래로 공간이 채워지고, 스택 영역에 데이터가 할당될수록 아래 -> 위로 공간이 채워집니다.
메모리 시스템은 효율적인 자원 사용을 위해 최소한의 빈 공간을 유지하려고 합니다.
그런데, 재귀 호출이 깊어질수록 스택 프레임이 계속 쌓이게 되면서 메모리의 끝에 다다르게 될 것입니다.
결국 스택 메모리의 한계를 초과하게 되면 프로그램은 스택 오버플로우에 의해 종료됩니다.
이렇게 재귀 알고리즘을 반복문으로 설정하는 것이 가장 간단한 방법이며, 반복문을 사용하면 스택을 사용하지 않기 때문에 깊은 재귀 호출에 의한 스택 오버플로우를 방지할 수 있습니다.
그 외 방법
-
꼬리 재귀 최적화:
자바는 꼬리 재귀를 직접 지원하지 않지만, 몇 가지 최적화 기법을 사용하여 재귀 함수를 변경하여 스택 오버플로우를 방지할 수 있습니다. 예를 들어, 재귀 함수의 결과를 인자로 전달하거나 상태를 갱신하는 방법을 사용하여 꼬리 재귀를 시뮬레이션할 수 있습니다. 하지만 이러한 최적화는 코드를 이해하기 어렵게 만들 수 있고, 모든 경우에 적용할 수 있는 것은 아닙니다. -
스택 크기 조정:
JVM의 스택 크기를 늘리는 것이 가능합니다. 이를 통해 재귀 호출이 깊게 중첩될 때 발생할 수 있는 스택 오버플로우를 방지할 수 있습니다. 이를 위해서는 JVM 옵션을 사용하여 -Xss 옵션을 설정하여 스택의 크기를 늘릴 수 있습니다. 예를 들어, -Xss4m과 같이 설정하여 4MB로 스택의 크기를 늘릴 수 있습니다. 하지만 이 방법은 재귀 호출이 깊게 중첩될 수 있는 경우에만 유효하며, 일반적으로는 권장되지 않습니다.
참고
심화
