[Kotlin] 코틀린에서 tailrec 을 사용하는 이유

코틀린에는 재귀 함수에 적용할 수 있는 tailrec 이라는 키워드가 있다.

tailrec 에 대해 공부하면서
tailrec 을 사용하는 이유를 좀 더 구체적으로 알아내기 위해 고민한 내용들을 공유해보고자 한다.

재귀 함수와 반복문

tairec 에 대해 알아보기 전에 재귀 함수 에 대해 간단히 살펴보자

 

재귀 함수 란 함수 안에서 자기 자신을 다시 호출하는 함수를 말한다.

1 부터 5 까지 더하는 작업을 재귀 함수 를 이용하면 다음과 같이 작성할 수 있다.

add(1)

fun add(num: Int): Int {
    return if (num == 5) num else num + add(num + 1)
}

 

위 함수의 실행 과정을 그림으로 표현하면 아래와 같다.

따라서 add(1) 이 한 번 수행될 때 총 5 개의 스택 프레임이 생성된다는 것을 알 수 있다.

 

하지만 위와 같은 단순 반복 작업의 경우
반복문 을 사용하는 것이 성능과 가독성 측면에서 모두 좋다.

var num = 0

for (i in 1..5) {
    num += i
}

 

그렇다면 재귀 함수가 더 유용할 때는 언제일까?

// dfs
dfs(1) // 출발지: 1

fun dfs(v: Int) {
    if (visited[v]) return

    visited[v] = true

    for (v 에서 이동 가능한 다른 모든 경로) {
        dfs(다음 경로)
    }
}

대표적으로 dfs 를 구현하는 경우가 있다.

dfs 는 완전 탐색 알고리즘 중 하나로
가능한 모든 경로를 탐색할 때까지 탐색 작업을 반복 수행하는 방식이다.

 

만약 반복문 만을 사용하여 dfs 를 구현하면 어떻게 될까?

dfs(1) //출발지: 1

fun dfs(v: Int) {
    val stk // v 에서 이동 가능한 경로 스택

    var next
    while (stk 가 비어있지 않은 한) {
        next = stk.pop()
        if (visited[next]) continue

        visited[next] = true
        for (next 에 이동 가능한 다른 모든 경로) {
            stk.push(다음 경로)
        }
    }
}       

보다시피 기존에 비해 코드가 복잡해진다.

 

재귀 함수 의 경우 함수를 타고 들어갈 때마다 스택 프레임 이 생성되기 때문에
함수 진입-탈출이 곧 하나의 탐색 경로로 이용되지만

 

반복문 에서는 탐색 경로에 대한 정보가 없기 때문에
별도로 탐색 경로를 저장하는 Stack 을 추가해줘야 한다.

 

따라서 이 경우에는 재귀 함수 를 사용하는 것이
가독성 측면에서 더 좋은 선택이라고 할 수 있다.

 

정리하면

반복 작업을 수행하기 위해 재귀 함수 또는 반복문을 사용할 수 있으며
상황에 따라 각각의 장단점이 존재하기 때문에 적절히 선택하여 사용하는 것이 좋다

tailrec

tailrec 은 Tail Recursion 을 의미하는 키워드로 꼬리 재귀 라고도 불린다.

 

tailrec 은 재귀 함수 와 함께 사용되며
tailrec 이 붙은 재귀 함수 는 컴파일 과정을 거치면서 반복문 으로 변환된다.
(이 때 재귀 함수 의 마지막 작업은 항상 재귀 함수 자신을 호출하는 작업이여야 한다.)

 

앞서 1 부터 5 까지 더하는 재귀 함수 에 tailrec 을 적용해보겠다.

tailrec fun add(num: Int, currentSum: Int = 0): Int {
    return if (num > 5) currentSum else add(num + 1, currentSum + num)
}

tailrec 을 사용하기 위해서는 마지막 작업이 항상 함수 자신을 호출하는 작업이여야 하기 때문에

중간 결과를 저장하기 위해 currentSum 을 추가해준다.

 

디컴파일해보면 재귀 함수 의 반복 작업 과 반복 시점 을
반복문으로 적절히 변환한 것을 확인할 수 있다.

이쯤에서 이런 물음이 생긴다.

왜 코틀린에서는 애써 만든 재귀 함수를 반복문으로 변환할까?

 

이에 대한 답은

앞서 설명한 재귀 함수와 반복문의 차이 를 통해 얻을 수 있다고 생각한다.

 

재귀 함수 는 가독성을 높여줄 수 있지만
스택 프레임 을 반복적으로 생성하기 때문에 스택 오버 플로우(Stack Over Flow) 를 발생시킬 수 있다.

 

반복문 은 가독성이 떨어질 수 있지만
스택 프레임 을 생성하지 않기 때문에 스택 오버 플로우 로부터 안전하다.

 

따라서 tailrec 은 재귀 함수의 가독성 과 반복문의 안정성 을 모두 챙기기 위해 존재하는 기능이라고 볼 수 있다.

결론

tailrec 은 재귀 함수 와 반복문 의 차이를 이용해

가독성 과 프로그램 안정성 을 제공해주는 기능이라는 것을 배울 수 있었다.

 

하지만 상황에 따라서는 재귀 함수 를 사용하는 것이 오히려 가독성 을 떨어트리는 선택이 될 수 있기 때문에

반복 작업 을 구현할 때는 항상 어떤 선택이 더 나을지를 고민하고 판단하는 것이 좋을 것 같다.