[Kotlin] Tail Recursive Function

0. 꼬리 재귀 함수

• 기존의 재귀함수는 모든 재귀 호출이 완료될 때까지는 결과를 얻을 수 없었으나, 꼬리 재귀에서는 계산이 먼저 수행되고, 재귀 호출이 수행되는 구조이다.
• 컴파일러가 stackoverflow가 발생하지 않도록 효율적인 순환 기반의 버전으로 최적화 해준다.
• 마지막으로 수행하는 구문이 자신을 호출하는 구문이어야 하며 재귀 호출 후 다른 코드가 있으면 사용할 수 없다.
• 꼬리 재귀 함수를 사용하지 않는 경우는 아래와 같은 경우인데 n*factorial(n - 1) 이 마지막 작업이 아니기 때문이다.

 

이미지 1

 

 

• 다음은 fibonacci(n-1, b, a+b)를 마지막 작업으로 두고 작성한 함수이다.

 

이미지 2

 

• 이미지 2에서 n에 100을 대입하면 정상 작동한다. 그러나 10000을 대입하면 StackOverflow가 발생한다.
• StackOverflow 문제를 해결하기 위해서는 아래와 같이 꼬리 재귀 함수를 의미하는 tailrec 을 함수 앞에 붙여주면 된다.

 

 

• 10000을 대입해도 StackOverflow가 일어나지 않고 정상 작동한다.