[Kotlin] tailrec 꼬리재귀

알고리즘 문제를 풀다가 알게 된 녀석

문제 : 콜라츠추측

프로그래머스

 

이 문제의 키워드는 '오버플로 Overflow' 이다.

오버플로 Overflow

넘쳐 흐른다는 뜻으로,
컴퓨터의 메모리가 8비트의 데이터를 저장할 수 있다고 하고, 편의상 부호는 없는 양수인 경우만 고려해 보자. 가장 작은 값은 0000 0000 (=0) 이며, 1씩 증가시키면 0000 0001 (=1)을 거쳐 최댓값인 1111 1111 (=255)에 도달하게 된다. 여기에서 1을 다시 한번 더하게 되면 최댓값의 범위를 넘어서게 되고, 최솟값인 0000 0000 (=0) 으로 되돌아가게 된다. 이를 오버플로 라고 부른다. (출처 : 나무위키)

 

예시로 626331이 주어졌을 때,

타입을 정수로 두면 계산을 하다 정수 범위(-2,147,483,648 ~ 2,147,483,647)를

넘기게 되어 오버플로가 발생한다.

오버플로가 발생하여 값이 음수로 변해도 코드는 그대로 실행된다.

그렇게 예상하지 못한 값이 반환되었다.

그래서 Int 보다 더 큰 타입인 Long으로 처리해주어 해결했다.

 

문제를 다 풀고 나면 다른 사람들은 어떻게 풀었는지 확인을 꼭 하는데

제일 상단에 있는 답을 보게 되었고, 처음보는 키워드가 있어 찾아보았다.

 

tailrec

Kotlin은 꼬리 재귀라고 알려진 함수형 프로그래밍 스타일을 지원합니다. 일반적으로 루프를 사용하는 일부 알고리즘의 경우 스택 오버플로 위험 없이 재귀 함수를 대신 사용할 수 있습니다. 함수가 tailrec 수정자로 표시되고 필수 형식 조건을 충족하면 컴파일러는 재귀를 최적화하여 대신 빠르고 효율적인 루프 기반 버전을 남깁니다.

 

재귀를 최적화해주는 수정자라고 한다....

그래서인지 다른 사람들의 답에 재귀함수가 많이 보였는데 (본인은 루프로 문제를 풀었다.)

코틀린에서 이러한 것을 제공해주는 지는 몰랐다.

이제라도 알아서 다행!

 

설명에 필수 형식 조건을 충족해야한다고 적혀있는데,

조건은 함수가 수행하려는 마지막 작업으로 자신을 호출해야한다는 것이다.

그렇지 않으면 해당 꼬리재귀를 사용할 수 없다고 한다.

 

tailrec 수정자를 사용하여 수정한 답은 다음과 같다.

---

공부하며 작성된 글이라 잘못된 정보가 있을 수 있습니다.

말씀해주시면 수정하겠습니다. 감사합니다.

References

아래 글을 참고하여 작성 되었습니다.

Functions | Kotlin