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

꼬리재귀 최적화

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


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)
}

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