[Swift][Algorithm]꼬리 재귀
19 August 2015
꼬리 재귀(Tail Recursion)
꼬리 재귀는 함수를 호출하면서 스택을 재사용합니다. 일반적인 재귀는 스택이 쌓이고, 호출되지 않으면 스택을 하나씩 정리합니다. 하지만 꼬리 재귀는 스택이 쌓이지 않기 때문에 메모리를 아낄 수 있습니다.
꼬리 재귀는 컴파일 때 보다 런타임 때에 이득을 얻습니다. 재귀를 사용할 것인지, 꼬리 재귀를 사용할 것인지는 문제에 따라 또는 넘겨주는 인자의 관계에 따라 적절하게 판단하여 사용하면 됩니다.
// 꼬리 재귀
func tailfactorial(x: Int, fac: Int) -> Int {
if x == 1 {
return fac
}
return tailfactorial(x-1, x * fac)
}
// 일반적인 재귀
func recfactorial(x: Int) -> Int {
if x == 1 {
return 1
}
return x * recfactorial(x-1)
}
tailfactorial(10, 1) == recfactorial(10) // true