[3장 재귀] 3.6 상호 재귀를 꼬리 재귀로 최적화하기

상호 꼬리 재귀 = 상호 재귀 + 꼬리 재귀

상호 재귀 : 함수A가 함수B를 호출하고, 함수B가 함수A를 호출하는 상황. (A -> B, B -> A)

예시 : odd, even 함수. odd(999) -> even(998) -> odd(997)... 이런식으로

상호꼬리재귀를 가능하게 하려면 트램펄린(trampoline)을 사용해야 한다고 한다. 스칼라나 클로저 같은 함수형 언어들은 자체적으로 트램펄린을 위한 타입과 기능을 내장하지만, 코틀린은 그러지 못한다고 한다. 그리고 free nomad(이후에 배울 것같다)로 트램펄린 자체를 하나의 타입으로 추상화한다고 한다.

trampoline 함수

sealed class B<A>
data class Done1<A>(val result : A) : B<A>()
data class More1<A>(val thunk : () -> B<A>) : B<A>()
tailrec fun <A> jump(bounce : B<A>) : A = when(bounce) {
    is Done1 -> bounce.result
    is More1 -> jump(bounce.thunk())
}

재귀로 더 호출해야한다면 More1이다. Done1은 최종적으로 반환해야 할 결과인 result를 매개변수로 받는다고 한다.

바로 연습문제로 보며 이해해보자. (사실 아래의 트램펄린함수는 상호 재귀라고 볼 수 없을 것같다.)

/*
	연습문제 3-18 : trampoline 함수를 사용하여 연습문제 3-17의 함수를 다시 작성해보자.
    연습문제 3-17 : 입력값 n의 제곱근을 2로 나눈 값이 1보다 작을 때까지 반복하고, 
    최초의 1보다 작은 값을 반환하는 함수를 상호 재귀를 사용하여 구현하라.
*/
import kotlin.math.sqrt
fun main(){
    println(jump(getSqrt1(4.0)))
}

sealed class B<A>
data class Done1<A>(val result : A) : B<A>()
data class More1<A>(val thunk : () -> B<A>) : B<A>()
tailrec fun <A> jump(bounce : B<A>) : A = when(bounce) {
    is Done1 -> bounce.result
    is More1 -> jump(bounce.thunk())
}
fun getSqrt1(num : Double) : B<Double> {
    when {
        num < 1 ->  return Done1(num)
        else -> {
            println("getSqrt $num -> ${sqrt(num)}")
            val ret : Double = sqrt(num)
            return More1{ divideTwo1(ret) } 
        }
    }
}
fun divideTwo1(num : Double) : B<Double> {
    println("divide two : $num -> ${num/2}")
    return More1 { getSqrt1(num/2)}

본래 코드에서(트램펄린을 사용하지 않는) getSqrt1 함수와 divideTwo1는 

fun divideTwo(num : Double) : Double {
    return getSqrt(num/2)
}
fun getSqrt(num : Double) : Double {
    when{
        num < 1 -> return num
        else -> {
            val ret : Double = sqrt( num.toDouble())
            return divideTwo(ret)
        }
    }
}

이런 구조를 가지고 있다.

트램펄린의 장점은 꼬리 재귀와 동일하게 스택오버플로우가 발생하지 않는 것이다.

상호재귀를 기본적인 방법으로 최적화할 수 없기때문에 트램펄린을 사용하는 것이다. 

 

 

참고 문헌

코틀린으로 배우는 함수형 프로그래밍 (조재용, 우명인 지음) 인사이트