Kotlin - tailrec(꼬리재귀)에 대해서 알아보기

kotlinbasic

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

자신만 반복적으로 호출하는 재귀함수(tailrec)는 while과 같이 루프를 사용하는 코드로 변환이 가능합니다. 이렇게 변환하면 좋은 점은 재귀함수가 호출되면서 소비되는 스택을 아낄 수 있다는 점입니다. 루프는 동일한 결과를 출력하면서 재귀함수보다 더 적은 자원을 사용하게 됩니다.

코틀린에서 tailrec 키워드가 있습니다. 이 키워드가 붙은 함수가 꼬리재귀 함수라면 코드가 컴파일될 때 루프를 사용한 코드로 변경됩니다.

재귀와 꼬리재귀 함수의 차이점에 대해서 알아보고, tailrec 키워드로 함수들이 어떻게 컴파일되는지 알아보겠습니다.

재귀함수와 꼬리재귀(tail recursive)

아래의 factorial은 재귀함수로 구현되었고, 재귀함수가 스스로 자신만을 호출하다 값을 리턴하는 구조이기 때문에 꼬리재귀(tailrec)라고 할 수 있습니다.

fun factorial(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        factorial(n-1, n*acc)
    }
}

fun main(args: Array<String>) {
    println("factorial(10) : ${factorial(10, 1)}" )
}

반면에 아래 재귀함수는 꼬리재귀가 아닙니다. 자신만을 반복적으로 호출하지 않고 1 + 재귀함수와 같은 추가적인 연산을 수행합니다. 그렇기 때문에 꼬리 재귀함수가 아닙니다.

fun factorial_plus_n(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        1 + factorial_plus_n(n-1, n*acc)
    }
}

tailrec 사용 방법

꼬리재귀인 factorial 함수에 tailrec이라는 키워드를 붙이면 컴파일러가 꼬리재귀를 루프를 이용한 코드로 변경해 줍니다.

tailrec factorial(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        factorial(n-1, n*acc)
    }
}

하지만 꼬리재귀가 아닌 함수에 tailrec 키워드를 붙여도, 루프 코드로 변경되지 않습니다.

tailrec fun factorial_plus_n(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        1 + factorial_plus_n(n-1, n*acc)
    }
}

일반 재귀함수에 tailrec이 붙은 코드를 컴파일을 해보면 tailrec 키워드가 붙었지만 꼬리재귀가 아니라는 경고가 발생합니다.

Warning:(11, 1) Kotlin: A function is marked as tail-recursive but no tail calls are found

바이트코드 비교

실제로 어떻게 컴파일되는지 확인해보기 위해 바이트 코드를 비교해보았습니다.

먼저 꼬리재귀이지만 tailrec 키워드가 붙지 않은 함수입니다.

fun factorial(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        factorial(n-1, n*acc)
    }
}

바이트 코드는 아래와 같고, 함수 내부에 INVOKESTATIC main/kotlin/Kotlin1Kt.factorial (II)I를 호출하는 코드가 있습니다. 바이트 코드는 잘 모르지만, 재귀적으로 함수가 계속 호출될 것으로 예상이 되네요.

public final static factorial(II)I
 L0
  LINENUMBER 4 L0
  ILOAD 0
  IFGT L1
 L2
  LINENUMBER 5 L2
  ILOAD 1
  GOTO L3
 L1
  LINENUMBER 7 L1
 FRAME SAME
  ILOAD 0
  ICONST_1
  ISUB
  ILOAD 0
  ILOAD 1
  IMUL
  INVOKESTATIC main/kotlin/Kotlin1Kt.factorial (II)I
 L3
  LINENUMBER 4 L3
 FRAME SAME1 I
  IRETURN
 L4
  LOCALVARIABLE n I L0 L4 0
  LOCALVARIABLE acc I L0 L4 1
  MAXSTACK = 3
  MAXLOCALS = 2

바이트 코드는 보기 힘드니, 이 코드를 다시 자바로 변환해서 확인해볼께요.

Jadx라는 툴을 이용하면 바이트코드(.class)를 자바 코드로 변환할 수 있습니다. (Jadx 툴 사용법은 'Android 앱(apk)을 decompile하는 방법'을 참고해주세요)

java로 변환된 코드를 보니, 재귀함수로 되어있습니다. tailrec 키워드를 붙이지 않으면 임의로 루프 코드로 변경하지 않는 것을 알 수 있었습니다.

public static final int factorial(int n, int acc) {
    if (n <= 0) {
        return acc;
    }
    return factorial(n - 1, n * acc);
}

다음은 tailrec 키워드가 붙은 꼬리재귀입니다.

tailrec fun factorial(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        factorial(n-1, n*acc)
    }
}

fun main(args: Array<String>) {
    println("factorial(10) : ${factorial(10, 1)}" )
}

바이트 코드는 다음과 같고, 함수 내부에 재귀적인 호출이 없습니다.

public final static factorial(II)I
 L0
  LINENUMBER 4 L0
 FRAME SAME
  ILOAD 0
  IFGT L1
 L2
  LINENUMBER 5 L2
  ILOAD 1
  GOTO L3
 L1
  LINENUMBER 7 L1
 FRAME SAME
  ILOAD 0
  ICONST_1
  ISUB
  ILOAD 0
  ILOAD 1
  IMUL
  ISTORE 1
  ISTORE 0
  GOTO L0
 L3
  LINENUMBER 4 L3
 FRAME SAME1 I
  IRETURN
 L4
  LOCALVARIABLE n I L0 L4 0
  LOCALVARIABLE acc I L0 L4 1
  MAXSTACK = 3
  MAXLOCALS = 2

위의 바이트 코드를 자바로 변환하여 확인해보면 tailrec이 붙은 factorial은 루프로 변경되어 컴파일 된 것을 볼 수 있습니다.

public static final int factorial(int n, int acc) {
    for (int n2 = n; n2 > 0; n2--) {
        acc *= n2;
    }
    return acc;
}

정리

꼬리재귀(tail recursive)와 재귀함수의 차이점에 대해서 알아보았습니다. 그리고 tailrec 키워드가 꼬리재귀를 자원 소비가 적은 루프 코드로 컴파일하는 것을 도와줍니다. 실제로 루프 코드로 컴파일되는지 확인하기 위해 tailrec 키워드가 붙은 꼬리재귀와 일반 꼬리재귀의 바이트 코드를 서로 비교해 보았습니다.

Loading script...

Related Posts

codechachaCopyright ©2019 codechacha