피보나치 수열의 일반항을 꼬리재귀로 만들기

트램폴린을 이용한 피보나치 일반항 함수 최적화

사실 이 문제는 피보나치 수열의 일반항을 구하는 재귀 함수를 어떻게 꼬리 재귀로 바꾸느냐가 핵심 아이디어임.

트램폴린 기법을 써서 피보나치 일반항 함수를 최적화해보자. 그러려면 우선 피보나치 일반항을 구하는 함수를 작성해보자.


func fib(n: Int) -> Int { guard n > 1 else { return n } return fib(n: n-1) + fib(n: n-2) }

위 함수는 다들 알겠지만, 숫자가 조금만 커지면 성능이 극도로 나빠진다. 이를 극복하기 위해서 (이전에 설명했듯이) 메모이제이션을 하는 것도 방법이지만, 꼬리재귀 최적화를 통해서 성능을 향상시키는 방법도 있다. 위 함수는 어떻게 꼬리재귀 형태로 바꿀 수 있을까? 보통의 꼬리 재귀의 경우에는 누적값 파라미터를 하나 더 넣어준다. 그런데 여기서는 누적값을 추적하기 위해서 파라미터가 두 개가 되어야 한다.

func fib(n: Int) -> Int {
    func helper(_ n: Int, _ a: Int = 1, _ b: Int = 0) -> Int {
        guard n > 0 else { return b }
        return helper(n-1, a + b, a)
    }
    return helepr(n)
}

실질적인 계산은 helper 함수가 수행하는데, 이 함수의 구조는 사실상 반복문을 이용한 구조와 동일하다. 따라서 허접하게 재귀로 짜놓은 코드와는 비교하기 어려운 속도를 낸다. 물론 속도 면에서는 그냥 루프로 하는 것만큼이나 빠를까만…

/*
0
1
1
2
3
5
8
...
956722026041
time: 0.052ms
*/

이제 트램폴린을 적용해보자.


enum Result<A, B, C> { case done(C) case call(A, B, C) } func fib(n: Int) -> Int { func helper(_ n: Int, _ a: Int = 1, _ b: Int = 0) -> Result<Int, Int, Int> { guard n > 0 else { return .done(b) } return .call(n-1, a + b, a) } var result = helper(n) while true { switch result { case let .done(r): return r case let .call(x, y, z): result = helper(x, y, z) } }

수행결과이다.

timeit{
    for i in 0..<60 {
        print(fibs(n: i))
    }
}

/*
0
1
1
2
3
5
8
...
956722026041
time: 0.297ms
*/

같은 결과물을 메모아이징으로 하면 당연히 이쪽이 결과는 좀 더 좋다. (왜냐면 앞의 항까지는 다 계산해놨으니까) Xcode8 Beta4의 기준에 맞게 메모아이징 함수를 약간 수정해보자.

func memoize<A: Hashable, B> (body: @escaping ((A) -> B , A) -> B) -> (A) -> B {
    var cache = [A:B]()
    var result = ((A) -> B)!
    result = { n in 
        if let r = cache[n] { return r }
        let r = body(result, n)
        cache[n] = r
        return r
    }
    return result
}

let fib2: (Int) -> Int = memoize{ fib, n in 
    if n < 2 { return n }
    return fib(n-1) + fib(n-2)
}

timeit{
    for i in 0..<60 {
        print(fib2(i))
    }
}

/*
0
1
1
2
3
5
8
...
956722026041
time: 0.179ms
*/

// 특이한 점은 트램폴린을 이용한 풀이에서 최종 항만 계산했을 때 보다 빠르다는 점이다. 
// 또한 특이한 점은 앞항의 계산결과를 이미 저장하고 있지만,
// 메모아이징 된 함수보다 그냥 루프로 돌린 계산이 더 빠르다는 점이다. (아마 여기서 모종의 최적화가 들어가지 않았을까....

파이썬 적용

사실 이 아이디어는 파이썬에 적용하기 쉽다. 특이한 점은 트램폴린을 이용하면 (파이썬은 꼬리재귀 최적화가 없음에도 불구하고) 꼬리재귀보다 더 빠른 속도를 보인다는 것이다.

def fibs_tail(n: int) -> int:
    def helper(x: int, y: int=1, z: int=0):
        if x < 2:
            return z
        return helper(x-1, y+z, y)
    return helper(600)

def fibs_tram(n: int) -> int:
    def helper(x: int, y: int=1, z: int=0):
        if x < 2:
            return z
        return (x-1, y+z, y)

    result = helper(n)
    while True:
        if isinstance(result, int):
            return result
        result = helper(*result)

print(fibs_tram(1600))