재귀 함수와 메모리 사용량 관계 _ 꼬리 재귀

재귀 함수는 반복하여 매서드를 호출한다.

그 과정에서 지역 변수, 매개 변수, 반환 값을 모두 process stack에 저장하게 된다.

 

이러한 과정은 반복문보다 더 많이 메모리를 사용하기 때문에, 성능이 좋지 않다.

스택 오버플로우를 일으킬 위험이 있다.

 

 

이러한 단점을 보완하기 위한 최적화 방법이 바로 꼬리 재귀이다.

 

꼬리 재귀는 재귀 호출이 끝난 후, 현재 함수에서 추가적인 연산을 요구하지 않는 재귀의 형태이다.

이는 컴파일러가 선형으로 코드를 처리하도록 알고리즘을 바꿔서 스택을 재사용 가능하게끔 한다.

단, 컴파일러가 이 기능을 지원해야 사용 가능하다.

 

다음 코드를 예시로 일반적인 재귀 함수와 꼬리 재귀를 파악해보자.

좌 : 일반적인 재귀 함수 이용 / 우 : 꼬리 재귀 이용

 

위 두 코드 모두 같은 결과를 출력한다.

 

좌측의 일반적인 재귀 함수는 스텍이 계속 쌓이게 되는 반면에, 우측 꼬리 재귀 함수는 한 번만 호출이 될 것이다.

좌측은 반환 값이 함수이기 때문에, 계속해서 함수를 호출하지만,
우측의 꼬리 재귀는 함수를 호출하고 그 함수를 변수에 할당하고 사용한다.
즉, 함수에서 추가 연산이 일어나지 않는다.

 

 

이처럼, 스텍이 계속 쌓이고 메모리 사용량이 늘어나는 단점을 보완한 것이 꼬리 재귀 함수이다.