꼬리재귀 최적화

꼬리재귀와 트램폴린

by sooopd
2016-10-272023-02-17
Swift, 스터디

꼬리 재귀(tail recursion)는 함수가 내부에서 자신을 재귀 호출할 때, 재귀 호출한 결과를 그대로 리턴하는 모양을 만드는 것이다. 이는 return 구문의 모양에 의해서 쉽게 판별할 수 있고, 재귀 호출의 결과 값에 대해서 추가적인 처리를 하지 않기 때문에 컴파일러가 쉽게 최적화할 후 있다. 재귀 호출의 결과를 그대로 사용한다는 것은, 재귀 호출을 수행하는 시점에 함수 내부의 지역 변수를 더 이상 사용하지 않는 것을 의미하므로 함수 호출에 의한 새로운 스택 프레임을 생성하는 대신, 현재 스택 프레임을 재활용할 수 있다. 따라서 꼬리 재귀는 반복 연산의 모양으로 변환이 가능하며, 이 과정은 기계적으로 처리될 수 있다.

꼬리 재귀는 컴파일러가 꼬리재귀 최적화를 지원하지 않는다면, 재귀 깊이에 한계가 있다는 단점이 있다. 따라서 재귀 호출 자체를 직접적인 반복문으로 변경할 수 있도록 재귀 호출을 수행할 함수를 리턴하는 것으로 스택 오버플로우를 회피할 수 있다.

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

꼬리재귀 최적화

꼬리재귀는 재귀의 특별한 한 형태인데, 재귀호출로 받은 결과값을 추가로 계산하거나 처리하지 않고 그대로 리턴하는 형태를 말한다. 예를 들어 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의 꼬리 재귀

by sooopd
2015-03-242023-02-20
Swift, 스터디

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