[Swift] 꼬리재귀(tail-recursive, tail call), 트램폴린(trampoline)

꼬리 재귀 (tail recursion)

• 함수가 자신을 재귀호출한 결과를 바로 리턴
  • 스택을 계속 생성할 필요 없이 함수의 첫 부분으로 되돌아 가는 것으로 실행 흐름을 대체

// 코드 출처
// https://soooprmx.com/%EA%BC%AC%EB%A6%AC%EC%9E%AC%EA%B7%80-%EC%B5%9C%EC%A0%81%ED%99%94%EC%99%80-%ED%8A%B8%EB%9E%A8%ED%8F%B4%EB%A6%B0/

// 일반적인 재귀
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의 꼬리재귀 최적화

• Swift 컴파일러는 꼬리 재귀 최적화를 수행하지만, 예외 상황이 있음
  • ARC로 인해, 컴파일러가 최적화를 수행하는 이전 단계에서 메모리 관리 코드를 삽입할 수 있음 → 기존의 소스 코드에서 꼬리 재귀 형태였던 것이 ARC에 의해 변형되며 꼬리 재귀 최적화를 받지 못하는 경우가 생김
  • 클래스 타입의 객체 메소드를 재귀호출하는 경우, 호출되는 메소드가 실행 시점에 동적으로 변경될 수 있음

트램폴린

• 자신을 반복 호출한 뒤, 다시 리턴을 반복하는 재귀와는 달리, 함수 호출 뒤 그 결과를 받아 다시 함수를 호출하는 방식
• 명시적으로 재귀를 루프로 바꿈
  • 최적화가 훨씬 쉬움
  • 꼬리 재귀 최적화를 지원하는 다른 언어에서도 문법적으로 구현이 가능하다면 실제 꼬리 재귀보다 좋은 성능을 보임

// 코드 출처
// https://soooprmx.com/%EA%BC%AC%EB%A6%AC%EC%9E%AC%EA%B7%80-%EC%B5%9C%EC%A0%81%ED%99%94%EC%99%80-%ED%8A%B8%EB%9E%A8%ED%8F%B4%EB%A6%B0/

enum TrResult<A, B> {
		case Done(B)
		case Call(A, B)
}

func trampolinize<A, B> (body: (A, B) -> TrResult<A, B>) -> (A, B) -> B {
		  return { n, acc in
				    while true {
						      switch body(n, acc) {
								        case .Done(r): return r
								        case .Call(x, y): res = body(x, y)
						      }
				    }
		  }
}

let sum3: (Int, Int) -> Int = trampolinize { n, acc in
		  if n < 1 { return .Done(acc) }
		  return .Call(n - 1, n + acc)
}

 

 

[Swift][Algorithm]꼬리 재귀

 

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

 

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