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

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

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

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


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

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