[Kotlin] 재귀 함수와 반복문, 그리고 꼬리 재귀(tailrec)

Kotlin

adorecamus 2023. 12. 12. 12:11

프로그래머스 콜라츠 추측 문제를 풀다가 다른 사람의 풀이에서 tailrec 키워드를 처음 접했습니다.

그래서 재귀 함수와 반복문, 그리고 꼬리 재귀를 정리해보았습니다.

재귀 함수란 자기 자신을 계속 호출하는 함수입니다.

반복적으로 자기 자신을 부르면서 stack 영역에 쌓이기 때문에, 루프(반복문)에 비해 더 많은 자원을 소비하고 성능이 떨어집니다.

종료 조건을 제대로 설정하지 않은 경우 무한 재귀는 stack overflow가 발생하며 프로그램이 비정상 종료되는 반면, 루프는 무한 실행됩니다.

자원을 더 소비하더라도, 재귀 함수는 가독성 측면에서 뛰어납니다.

루프로 구현하는 것에 비해 더 적은 변수를 사용하면서도 코드량을 줄일 수 있습니다.

또 알고리즘을 효과적으로 표현합니다.

팩토리얼을 구현한 Java 코드 예시입니다.

// 반복문
public int factorial(int n) {
    int acc = 1;
    for (int i = n; i > 0; i--) {
        acc *= i;
    }
    return acc;
}

// 재귀 함수
public int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

이때 위의 재귀 함수를 이렇게도 바꿀 수 있습니다.

// 꼬리 재귀 함수
public int factorial(int n, int acc) {
    if (n == 1) return acc;
    return factorial(n - 1, n * acc);
}

이를 꼬리 재귀 함수라고 합니다.

꼬리 재귀(tail recursive) 함수는 추가적인 연산이 없이 자신 스스로 재귀적으로 호출하다가 어떤 값을 리턴하는 함수를 말합니다.

앞서 팩토리얼을 구현한 코드는 return 부분에서 차이가 있습니다.

재귀 함수는 추가적인 연산을 수행하지만(n을 곱함), 꼬리 재귀는 자기 자신만을 호출합니다.

Kotlin에서는 tailrec 키워드를 붙여 꼬리 재귀 함수를 루프로 컴파일되도록 할 수 있습니다.

재귀 함수로 코드를 작성해 가독성을 유지하면서도, 컴파일 과정에서 루프로 변환되어 성능이 떨어지지 않습니다.

팩토리얼을 다시 Kotlin으로 작성해보겠습니다.

// 꼬리 재귀 함수
tailrec factorial(n: Int, acc: Int): Int {
    return if (n == 1) {
        acc
    } else {
        factorial(n-1, n*acc)
    }
}

// 반복문
fun factorial(n: Int, acc: Int): Int {
    for (i in n downTo 1) {
        acc *= i;
    }
    return acc;
}

위의 두 코드는 같은 방식으로 컴파일되어 아래 코드보다 더 적은 자원을 소비할 것입니다.

// 재귀 함수
fun factorial(n: Int): Int {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

한편 위와 같이 꼬리 재귀가 아닌 재귀 함수에는 tailrec 키워드를 붙이더라도 루프로 컴파일되지 않습니다.

참고