Home » 꼬리재귀 최적화

꼬리재귀 최적화

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

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

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

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


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

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

꼬리재귀 최적화와 트램폴린

꼬리재귀 최적화

꼬리재귀는 재귀의 특별한 한 형태인데, 재귀호출로 받은 결과값을 추가로 계산하거나 처리하지 않고 그대로 리턴하는 형태를 말한다. 예를 들어 1부터 n 까지의 합을 구하는 함수를 재귀로 구현했다고 하면 일반적으로 다음과 같은 꼴을 생각할 수 있다.

<br />func sum1(n: Int) -> Int {
  if n < 1 { return 0 }
  return n + sum1(n - 1)
}

이를 꼬리 재귀로 만들면 다음과 같다.

func sum2(n: Int, acc: Int = 0) -> Int {
  if n < 1 { return acc }
  return sum2(n-1, acc: acc + n)
}

더 보기 »꼬리재귀 최적화와 트램폴린

꼬리와 꼬리재귀는 다르다. (Swift)

꼬리재귀 Natasha ElementTypehe Robot에 꼬리재귀에 대한 글이 올라오고 Digg에서 많은 digg을 얻었는데, 좀 이상해서 내용을 정리해본다. 링크한 글의 저자는 꼬리재귀와, 함수형 언어의 자료 구조인 리스트의 head, tail을 혼동하고 있는 듯 하다. 우선 꼬리재귀에 대해서 먼저 이야기하겠다. 꼬리 재귀는 재귀의 특별한 한 형태이다. 꼬리 재귀를 설명하기 전에 먼저 재귀(recursion)에 대해 알아보자. 재귀는 어떤 함수의 내부에서 스스로를 다시 호출하는 것을 말한다. 예를 들어서 1에서 10 까지의 자연수의 합을 구하는 과정을 재귀적인 처리를 통해서 구한다고 생각해보자. 계산은 1 + 2 + 3 +… 더 보기 »꼬리와 꼬리재귀는 다르다. (Swift)