[Basic] Tail Call, Tail Recursion

Tail Call

tail call에 대해서 알아보자.

fun foo() {
  var a = 10
  return bar(a)
}

fun bar(n: Int) {
  return n+1
}

fun main(args: Array<String>) {
  foo()
}

 

①main()이 foo()를 호출하면, ②본래는 foo()가 스택에 남아 있고 ③bar(a)를 계산한 후 ④그 값을 반환받아 ⑤foo()가 그 값을 반환하는 주체가 된다. 그런데 위와 같은 프로그램에서, 사실 foo()는 bar(a)의 값을 반환받은 후 아무것도 하지 않고 이를 그대로 돌려주기만 할 뿐이다. 곧, ②, ④, ⑤는 필요없는 과정인 셈이다. 다만, foo()가 bar()를 호출해놓고 사라져버리게 되면, main()로 값을 반환할 주체가 없게 된다. Kotlin과 같은 프로그래밍 언어는, bar(a)를 계산한 값이 곧바로 반환될 수 있도록 내부적으로 지원하는 것이다.

 

Tail Recursion

한편 보편적인 재귀의 경우, 모든 재귀 호출을 먼저 수행한 후, 마지막의 반환 값부터 결과를 계산해나간다. 따라서, 재귀 호출이 만들어질 때까지 결과를 얻을 수 없다. 이러한 비효율을 해결하고자 등장한 개념이 tail recursion으로서, Kotlin을 포함한 몇몇 프로그래밍 언어에서 지원된다.

tail recursion의 경우, 계산이 처음 수행되고, 그 후에야 재귀 호출이 실행된다(재귀 호출이 현재 단계의 결과를 다음 재귀 호출에 넘겨준다). 이는 재귀 호출을 반복문과 동일하게 만들어주며, 스택 오버플로우의 위험을 없앤다.

 

피보나치 함수를 예로 들어보자. 다음의 두 조건을 만족하는, 아래와 같은 함수가 tail recursion이라 할 수 있다.

 

▪ fibo() 함수 호출이 가장 마지막 연산이다.

▪ 키워드 tailrec을 통해서 컴파일러에게 tail recursion임을 알려준다.

tailrec fun fibo(n: Int, prevPrev: Long, prev: Long): Long {
    if (n == 2) {
        return prevPrev + prev
    } else if (n < 2) {
        return n.toLong()
    }

    var cur: Long = prevPrev + prev

    var prevPrev: Long = prev
    var prev: Long = cur

    return fibo(n - 1, prevPrev, prev)
}

fun main(args: Array<String>) {
    println(fibo(3, 0, 1))
}