꼬리 재귀 최적화 #45
Description
꼬리 재귀 최적화란 무엇인가요?
- 일반 재귀의 단점을 보완하여,
실행 속도또는메모리 사용량을 최적화하는 방법
일반 재귀의 단점은 무엇인가요?
- 기본적으로 재귀 함수는 다음 재귀 함수의 호출시 기존 재귀 함수의 정보(파라미터, 리턴값, 리턴 후 돌아갈 위치 등)을 스택(메모리 저장공간)에 쌓이게 되어, 반복문에 비해 많은 메모리를 차지한다. 만약, 재귀 함수를 너무 많이 호출하게 되면, 스택 공간이 모두 차버려서, 스택 오버플로우가 발생한다.
왜 "꼬리" 재귀라고 하는건가요?
- "꼬리 재귀 최적화"에서의 "꼬리(tail)"는 함수의 재귀 호출에서 반환되는 부분을 가리킨다.
- 재귀 함수에서는 기본적으로 현재 함수의 결과를 계산하기 위해, 자기 자신을 다시 호출하고 그 호출 결과를 반환한다.
- 이때, 함수가 종료되기 직전에, 이런 재귀 호출이 이루어지는 부분을 "꼬리(tail)" 부분이라고 한다.
- 이 꼬리 부분에서의 재귀 호출을 최적화하는 것을
꼬리 재귀 최적화라고 한다.
꼬리 재귀 최적화를 어떻게 하는건가요?
- 꼬리 재귀를 위한 조건은 아래의 두 가지가 있다.
- 재귀 함수를 꼬리 재귀 방식으로 구현
- 컴파일러가 꼬리 재귀 최적화를 지원
일반 재귀
- return시, 추가 작업 함.
public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1); // 반환값에 추가적인 연산이 필요
}
}꼬리 재귀
- 꼬리 재귀의 핵심은 반환(return)부에 연산이 없어야 한다는 점이다.
- 따라서, return시, 어떠한 연산을 하지 않고, 함수 자체를 반환하도록 코드를 작성해야 한다.
public static int factorialTailRecursive(int n, int accumulator) {
if (n == 0) {
return accumulator; // 최종 결과 반환
} else {
return factorialTailRecursive(n - 1, n * accumulator); // 다음 재귀 호출
}
}꼬리 재귀의 장점은 무엇인가요?
- 최적화된 꼬리 재귀 함수에서는 이 꼬리 부분에서의
반환 값을 다음 재귀 호출의매개변수로 전달함으로써 스택 프레임을 재사용한다. - 이렇게 스택 프레임을 재사용하기 때문에, 스택 메모리의 사용량을 줄일 수 있고, 실행 속도도 향상시킬 수 있다.
꼬리 재귀의 단점은 무엇인가요?
- 언어 차원에서 지원해줘야하는 불편함이 있다.
- 아무리, 코드를 꼬리 재귀로 작성하더라도, 컴파일러에서 지원 안하면 꼬리 재귀 최적화를 할 수 없다.
- 자바의 경우, 꼬리 재귀 최적화를 지원하지 않는데, 그래도 코딩시 꼬리 재귀 형태로 작성하는 것이 좋다는게
모던 자바 인 액션(p.583)에서 이야기한다. 왜냐하면, 꼬리 재귀 형태로 작성해 놓으면, 추후에 지원할 수도 있고, 꼬리 재귀 최적화가 아니더라도 다른 컴파일 최적화 방법을 활용할 수 있기 때문이다.
자바의 경우 왜 꼬리 재귀 최적화를 지원하지 않는가?
- 자바는 플랫폼 독립성, 안정성, 보안, 그리고 범용성을 중요하게 고려한 언어이다. 따라서 자바의 설계자들은 언어와 실행 환경을 가능한 한 다양한 플랫폼에서 사용할 수 있도록 만들기 위해 노력했다. 이러한 목표를 달성하기 위해 자바는 일관된 동작과 안정성을 보장하면서도 메모리 모델을 간단하고 예측 가능하게 유지하는 것이 중요하다.
따라서 꼬리 재귀 최적화를 지원하지 않는 것은 자바가 다양한 환경에서 일관된 동작을 유지하고, 복잡성을 최소화하면서도 안정성과 보안을 유지하기 위한 선택으로 해석할 수 있다. 이러한 설계 선택은 자바가 다양한 영역에서 범용적으로 사용될 수 있도록 하는데 기여한다.