[Kotlin] 재귀 함수의 꼬리 호출 제거(TCE): tailrec 키워드

꼬리 호출 제거(TCE, Tail Call Elimination)

• 함수가 제일 마지막에 하는 일이 자기 자신을 호출하는 것이라면, 즉, 재귀 호출의 결과를 다른 연산에 사용하지 않고 즉시 반환한다면, 코틀린이 이 꼬리 호출을 제거한다는 뜻이다.
• 아래 예제를 보며 이해해보자.
  • N을 입력으로 받아 1~N까지를 모두 더하는 함수를 만들어 보자.

    • fun sum(n: Int): Int {
          fun sum(s: Int, i: Int): Int = if (i <=0) s else {
                  println("s: $s, i: $i")
                  sum(s + i, i - 1)
          }
          return sum(0, n)
      }

    • sum(s: Int, i: Int) 함수는 재귀 호출 마지막에 1~N의 합을 뱉어내고 이는 그대로 함수의 리턴 값이 된다.
    • 위의 예제 코드는 공재귀이다. 
      • 공재귀: 한 단계의 출력을 다음 단계의 입력으로 사용하는 계산 단계를 합성한 것.
        • 일반적인 재귀 함수의 경우, 마지막 단계의 연산까지 도달한 후 연산을 시작하기  때문에 그때까지 모든 과정을 스택에 저장해야 한다. 즉, 이 경우 메모리가 부족하기 쉽다. 이 문제를 피하려면 재귀 대신 공재귀를 사용하는 것이 최선이다.
      • 함수가 자기 자신을 호출하면 스택에 넣은 내용이 그리 많지 않더라도 어쨌든 스택 공간을 사용하긴 한다.
        • 즉, 공재귀도 스택 공간을 사용하긴 한다.
        • 이 문제를 완전히 없애는 방법은 "공재귀 함수를 루프로 바꾸는 것"이다.
        • tailrec 키워드를 사용하면 코틀린이 자동으로 꼬리재귀 함수를 루프를 사용한 코드로 변경하여 컴파일한다.
  • 그렇다면 여기에 tailrec 키워드를 함수 앞에 붙여보자.

    • fun sum(n: Int): Int {
          tailrec fun sum(s: Int, i: Int): Int = if (i <=0) s else {
                  println("s: $s, i: $i")
                  sum(s + i, i - 1)
          }
          return sum(0, n)
      }

    • tailrec 키워드를 붙인 경우 결과가 달라지지는 않지만, 원치 않는 실수를 코틀린이 잡아줄 수 있다.
    • 다음과 같이 리턴 값이 재귀 호출 결과에 다른 연산을 추가한다면 노란 박스와 함께 다음의 메시지를 볼 수 있다.
      • "A function is marked as tail-recursive but no tail calls are found"

      • 

    • 꼬리 재귀가 아닌 일반 재귀 함수로 사용하는 경우 실행 시점에 StackOverflowException이 발생할 수 있다.
  • Q: 처음부터 루프로 구현하면 되는거 아닌가?????
    • A: 재귀 함수의 경우 메모리 제약이 있지만 코드 작성이 훨씬 쉽다는 큰 장점이 있다. 반복문으로 작성하다 보면 장황하게(?) 작성되는 경우가 많은데 그런 경우 상대적으로 코드를 이해하기도 힘들고 실수할 확률도 증가한다. 그렇기 때문에 위의 예제처럼 재귀 함수로 구현한 후, tailrec 키워드를 이용하는 방법을 적극 활용해보자.

 

 

StackOverflow 예방: tailrec  키워드를 사용해 루프로 컴파일

• 메모리 제약 대문에 재귀가 공재귀보다 덜 유용하다. 하지만 재귀는 작성이 훨씬 쉽다는 장점이 있다. 
• 예제: 양의 정수에 대해 작동하는 공재귀 add 함수
• 공재귀함수로 다음과 같이 구현할 수 있다.
  •  
  • fun inc(n: Int) = n + 1 fun dec(n: Int) = n - 1 fun add(x: Int, y: Int): Int = if(y==0) x else add(inc(x), dec(y)) fun main(args: Array<String>) { println(add(5000, 20000)) // StackOverflowError }
  • 공재귀함수이지만, 숫자가 어느 정도만 커져도 StackOverflow 에러가 발생한다.
• 하지만 여기에 tailrec 키워드를 붙여주면 해당 함수를 루프로 컴파일하기 때문에 StackOverflow 에러가 발생하지 않는다.

  • tailrec fun add(x: Int, y: Int): Int = if(y==0) x else add(inc(x), dec(y))
    
    fun main(args: Array<String>) {
        println(add(5000, 20000)) // 25000
    }

 

 

참고

- [코틀린을 다루는 기술]