[코파기 3부] 10. 코틀린과 꼬리재귀와 tailrec

 

 

꼬리재귀 (Tail Recursion)?

재귀함수는 함수가 자기 자신을 호출하는 함수를 의미합니다.

그 중에서도 꼬리재귀(Tail Recursion)는 재귀 함수 종류 중에서도

재귀 함수의 마지막 부분에서 자기 자신을 호출하는 재귀 함수를 의미합니다.

 

 

 

재귀함수의 대표적인 예시 중 하나인 팩토리얼을 갖고와봤습니다.

위 코드 같은 경우는 자기 자신을 호출하는 부분이 함수의 맨 마지막 줄이

n * fact(n-1)로, n을 곱하는 추가적인 연산이 있습니다.

 

 

 

마지막 줄에 n을 곱해주는 연산을 없애기 위해 인자를 하나 더 늘려

재귀 호출이 함수의 마지막 부분인 꼬리 재귀 형태로 만들었습니다.

 

 

 

재귀함수의 문제점?

재귀 함수는 간결하게 짤 수 있어 DFS 등에서 저도 애용하나,

몇 가지 문제점이 있습니다.

 

1. 때때로 반복문보다 이해하기 어렵다, 가독성이 떨어진다.

2. 재귀는 매 호출마다 스택에 새로운 프레임을 생성하므로, 스택 한계를 초과하면 스택 오버플로우 가능성이 있다.

3. 종료 조건이 명확하지 않다면 무한 루프에 빠질 수 있다

 

이번 포스팅에서 주의깊게 볼 것은 2번. 스택 오버플로우 가능성입니다.

while, for문 등에서는 반복 횟수 자체로는 스택 오버플로우가 발생되지 않습니다.

하지만 재귀함수에서는 동작 방식에서 스택을 이용하기에,

스택의 한계를 초과하면 반복횟수가 많다는 이유만으로 스택 오버플로우의 가능성이 있습니다.

 

 

 

 

 

Tailrec 키워드

 

 

 

 

tailrec 키워드는 위와 같은 재귀함수를 반복문으로 동작하게끔 해주는 키워드입니다.

함수의 마지막 부분에 별 다른 연산이 있어서는 안되고,

마지막 부분이 자기 자신인 꼬리 재귀 형태에서만 사용할 수 있습니다.

 

 

 

tailrec이 없을 때

 

 

 

10000을 입력으로 주었을 때, 스택 오버플러우 에러가 발생하였습니다.

 

재귀함수의 동작 원리 상, 이전에 호출한 함수가 종료되는 것이 아니라

첫 함수가 두 번째 함수를 호출하고,

두 번째 함수가 세 번째 함수를 호출하고,

세 번째가 네 번째... 다섯 번째가 여섯 번째를 호출하고...

종료 조건에 도달하면, 마지막으로 호출한 함수부터 종료되며,

그 직전에 호출된 함수가 종료되고, 또 그 직전에 호출된 함수 ... 2번째, 1번째로 호출된 함수가 종료됩니다.

 

이전에 호출된 함수가 남아있기 때문에 스택오버플로우가 발생할 수 밖에 없는 구조이죠.

현재 실행되는 함수를 스택 프레임(Stack Frame)에 저장하기에, 스택 오버플로우가 발생하는 것이고요.

 

 

 

tailrec을 붙였을 때

 

 

 

우측의 스크롤을 보면 알겠지만... 꽤 깁니다

 

Tailrec 키워드는 컴파일러가 내부적으로 재귀 함수를 반복문으로 최적화 해줍니다.

따라서 스택 오버플로우의 위험성에서 벗어날 수 있습니다.

 

또, 내부적으로 반복분으로 바꿔주므로

이전 함수가 남아있다는 재귀함수의 단점이 없으므로,

상대적으로 더 적은 리소스를 사용합니다.

 

 

 

후기

오랜만의 코파기 시리즈입니다.

어떤 언어든, 프레임워크든, 플랫폼이든,

정말 공부하면 공부할수록 공부해야 할 것이 나오네요.

 

이론적으로는 모든 재귀 함수는 반복문으로 구현하는 것이 가능합니다.

문제의 따라서는 재귀함수가 더 적합할 수 있겠지만,

재귀 함수를 꼬리 재귀로 구현하여 컴파일러가 반복문으로 최적화 하도록 하는 방식은 꽤 신기하네요.