꼬리 재귀(Tail Recursion)
꼬리 재귀란 재귀의 결과를 바로 반환하는 재귀 형태입니다.
말로 들으면 무슨 말인가 이해가 안 될 것이므로 코드로 알아보겠습니다.
아래 함수들은 단순히 1 ~ n까지의 합을 구하는 역할입니다.
먼저 일반 재귀 형태를 먼저 보겠습니다.
func recursion(_ num: Int) -> Int {
if num == 0 { return num }
return num + recursion(num - 1)
}파라미터로 num을 전달 받고 num + recursion 결과를 반환합니다.
이 메서드 안에는 num + recursion 이라는 연산이 존재합니다.
연산이 존재하면 연산을 위한 값을 스택에 저장해야하기 때문에
재귀를 할 때마다 스택에 메모리 할당이 발생합니다.
꼬리 재귀는 이 연산을 없애는 방법입니다.
func tailRecursion(_ num: Int, _ sum: Int) -> Int {
if num == 0 { return sum }
return tailRecursion(num - 1, sum + num)
}sum을 파라미터로 전달하여 메서드 안의 연산을 없앴습니다.
연산이 존재하지 않으므로 매번 새로운 값을 스택에 저장하지 않아도 됩니다.
그렇기 때문에 기존의 스택을 재활용하여 메모리 최적화가 발생합니다.
속도 비교
둘의 코드를 실제로 실행시켜보겠습니다.
둘의 수행 속도와 메모리 사용량을 비교해봤는데요.
재귀 횟수와 성능 차이가 비례할 것으로 생각해서 1000, 1만, 10만으로 횟수를 점점 늘리면서 비교해봤습니다.
순서대로 1천, 1만, 10만입니다.
확실히 꼬리 재귀가 더 빠르긴 합니다...만 의미가 있는 숫자는 아닌 거 같습니다.
Xcode로 메모리도 확인해보았지만 둘은 동일했습니다.
차이가 점점 커질 것으로 예상했지만 너무 똑같아서 당황했습니다.
특히 메모리는 차이가 클 것으로 예상했는데요 똑같다니요...
속도 차이가 안 나는 원인
그래서 왜 차이가 안 나는지 검색을 해보니 ARC가 원인이었습니다.
WWDC21 - ARC in Swift : Basics and beyond의 내용에 따르면 컴파일러는 retain과 release를 자동으로 삽입합니다.
이 과정에서 개발자가 꼬리 재귀로 코드를 작성해도 메모리 관리 코드가 삽입되면서 꼬리 재귀로 동작을 안 할 수도 있다고 합니다.
(근데 이건 상황에 따라 다른 거 같아요. 아직 정확한 정보는 찾지 못해서 혹시 아시는 분 계시다면 댓글로 말씀 부탁드립니다.)
꼬리 재귀 최적화 방법
꼬리 재귀의 형태는 트램폴린 기법으로 변형이 가능합니다.
트램폴린 기법은 함수 호출 뒤에 그 결과를 받아 다시 함수를 호출하는 방식입니다.
명시적으로 재귀를 루프로 바꾸는 것이죠.
트램폴린 기법으로 변형하면 실제 꼬리 재귀보다 훨씬 좋은 성능을 보입니다.
비교 스크린샷은 뒤에서 확인할 수 있습니다.
정말 놀랄 정도로 차이가 컸습니다.
다음은 트램폴린 기법으로 꼬리 재귀를 최적화한 코드입니다.
//꼬리 재귀 최적화 -> 열거형 + 클로저
enum TrampolineResult<T> {
case done(T)
case call(() -> TrampolineResult<T>)
}
func helper(num: Int, sum: Int) -> TrampolineResult<Int> {
if num == 0 { return .done(sum) }
return .call({ helper(num: num - 1, sum: sum + num) })
}
func trampolineTailRecursion(num: Int) -> Int {
var res = helper(num: num, sum: 0)
while true {
switch res {
case let .done(x):
return x
case let .call(function):
res = function()
}
}
}TrampolineResult 열거형에는 done과 call 케이스가 있습니다.
call 케이스는 함수를 연관값으로 전달받습니다.
helper 메서드는 재귀와 형태가 유사합니다.
종료 조건에서는 done을 반환하고, 재귀 조건에는 call을 반환합니다.
call의 연관값으로 호출할 메서드를 전달합니다.
trampolineTailReucursion에서는 실제 반복이 이뤄집니다.
helper의 반환값을 확인해서 done이 아니라면 계속 반복합니다.
call의 연관값으로 전달 받은 함수를 실행하여 재귀 호출을 수행합니다.
코드 자체만 보면 길이가 길어 어려워 보이지만 큰 틀은 일반 재귀와 다를 바 없습니다.
그럼 실제로 실행을 해보겠습니다.
10만부터 시작을 할게요.
시간만 비교하면 느리다는 걸 볼 수 있습니다.
위에서 재귀와 (꼬리 재귀로 동작 안 하는) 꼬리 재귀는 100만부터는 런타임 에러가 발생했습니다.
그렇다면 트램폴린 기법은 어떨까요?
100만은 물론이고 1억도 수월하게 수행이 됩니다.
속도는 횟수와 비례하게 10배씩 커지네요!
이로서 메모리 최적화는 확실히 확인이 되었습니다.
꼬리 재귀 최적화의 최적화
위에서 알아본 트램폴린 기법은 한 가지 아쉬운 점이 있습니다.
바로 클로저 생성 오버헤드입니다.
helper 메서드에서 call의 연관값으로 클로저를 생성하여 전달합니다.
클로저를 생성할 때도 비용이 소요되므로 오버헤드가 존재합니다.
이 클로저를 직접 생성하지 않고 함수 호출에 필요한 파라미터만 전달하여 한 번 더 최적화가 가능합니다.
//꼬리 재귀 최적화의 최적화 -> 클로저 생성 오버헤드 제거
enum TrampolineResult2<A, B> {
case done(B)
case call(A, B)
}
func helper2(num: Int, sum: Int) -> TrampolineResult2<Int, Int> {
if num == 0 { return .done(sum) }
return .call(num - 1, sum + num)
}
func trampolineTailRecursion2(num: Int) -> Int {
var res = helper2(num: num, sum: 0)
while true {
switch res {
case let .done(x):
return x
case let .call(num, sum):
res = helper2(num: num, sum: sum)
}
}
}call의 연관값으로 num과 sum을 전달 받습니다.
이전에는 실행할 함수를 call의 연관값으로 부터 전달 받아 수행했습니다.
하지만 지금은 파라미터 값만 전달받아 helper2 메서드를 직접 호출하고 있습니다.
클로저를 생성하지 않아도 이로 인한 오버헤드가 없어졌습니다.
최적화 트램폴린 기법 실행 결과
최적화 후의 결과는 큰 차이가 있을까요?
1~1억까지의 합을 트램폴린 기법 최적화 전후의 메서드를 사용해 구해봤습니다.
정말 놀라울 정도로 차이가 컸습니다.
딱 10배 차이가 나네요.
일반 재귀는 100만 회 재귀도 못하는데
최적화 트램폴린 기법으로는 1억 회의 재귀를 0.6초만에 완료했습니다.
마무리
오늘은 일반 재귀와 꼬리 재귀의 차이점, 꼬리 재귀를 트램폴린 기법으로 최적화하는 방법을 알아보았습니다.
꼬리 재귀가 유용한 것은 확실하지만, ARC에 의해 최적화가 안 될 수도 있다는게 무척 의외였습니다.
ARC가 마냥 좋은건 줄 알았는데 이런 부작용도 있었네요!
그리고 또 한번 직접 결과를 확인하는 것의 중요성을 깨달았습니다.
만약 이론만 보고 넘어갔다면 꼬리재귀로 해골물 마실 뻔 했습니다 ㅎㅎ;
같은 기능이라도 최적화 여부에 따라 천지차이의 성능 차이를 보여준다는 것도 알게 되었네요.
감사합니다.
참고
https://soooprmx.com/tail-recursion/
https://joooing.tistory.com/entry/재귀-→-꼬리-재귀-Tail-Recursion
https://academy.realm.io/kr/posts/swift-tail-recursion/
아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.