스위프트의 꼬리재귀

개요

스위프트에서는 꼬리재귀 최적화를 지원하는데요, 꼬리재귀가 무엇인지 어떠한 장점이 있는지 정리해봤어요.

꼬리재귀란 무엇인가요?

꼬리재귀는 프로그래밍에서 사용되는 재귀 호출의 특별한 형태에요.

꼬리재귀에서는 함수가 자신을 다시 호출할 때 이 재귀 호출이 해당 함수의 마지막 연산이며, 이후에 추가적인 작업이 없는 경우를 말해요.

 

즉, 함수의 반환 값이 다른 연산이나 표현식 없이 바로 재귀 호출의 반환 값과 동일하면, 그 함수 호출은 꼬리재귀 호출로 간주되죠.

// 일반 재귀
// 함수의 반환 값에 다른 연산이 포함되어 있다.
func recursion(_ num: Int) -> Int {
    if num == 0 { return num }
    return num + recursion(num - 1)
}

// 꼬리재귀
// 함수의 반환 값에 다른 연산이 포함되어 있지 않다.
func tailRecursion(_ num: Int, _ sum: Int) -> Int {
    if num == 0 { return sum }
    return tailRecursion(num - 1, sum + num)
}

꼬리재귀는 일반재귀와 뭐가 다른가요?

꼬리재귀는 일반재귀에 비해 여러 장점을 가져요.

1. 최적화: 컴파일러 또는 인터프리터는 꼬리재귀를 감지하고 꼬리재귀 최적화를 수행하게 돼요. 이 최적화를 통해 함수 호출 스택이 누적되지 않게 되어 재귀 함수의 호출 깊이가 깊어져도 스택 오버플로우가 발생하지 않아요. (자세한 과정은 밑에서 서술할게요.)
2. 성능: 꼬리재귀를 사용하면 추가적인 스택 프레임을 만들 필요가 없기 때문에 메모리 사용량이 줄어들고, 실행 속도가 향상될 수 있어요.
3. 간결성: 꼬리재귀를 사용하면 몇몇 알고리즘을 더 간결하게 표현할 수 있어요.

그리고 스위프트에서는 꼬리재귀 최적화(TCO, Tail Call Optimization)를 지원해요.

구체적인 꼬리재귀 최적화 과정

사실 위에서 언급한 1, 2번의 장점은 꼬리재귀 최적화 때문에 얻을 수 있는 이점이에요.

꼬리재귀 최적화를 지원하지 않는 컴파일러에서의 꼬리재귀는 그저 특정 형태의 재귀 호출일 뿐이죠.

 

구체적인 꼬리재귀 최적화 과정은 다음과 같아요.

1. 스택 프레임 재사용: 꼬리 위치에서의 함수 호출은 현재의 함수가 더 이상 수행할 작업이 없기 때문에, 현재 함수의 스택 프레임을 다음 함수 호출에 재사용할 수 있어요. 따라서 새로운 스택 프레임을 할당하고 초기화하는 오버헤드가 사라져요.
2. 변수 업데이트: 꼬리재귀 함수의 파라미터는 보통 이전 호출에서의 결과나 다음 단계의 입력 값으로 업데이트 돼요. 최적화 과정에서 이러한 변수 업데이트는 현재 스택 프레임의 변수를 직접 업데이트하는 것으로 처리될 수 있어요.
3. 점프 명령 사용: 일반적인 재귀 호출에서는 함수 호출 명령이 사용되지만, 꼬리재귀 최적화에서는 "점프" 또는 "분기" 명령으로 처리될 수 있어요. 즉, 사실상 루프 형태로 처리할 수 있죠.

마무리

잠깐 언급했듯이 꼬리재귀 자체는 재귀 호출의 특정 형태를 의미해요.

그리고 일부 컴파일러에서는 꼬리재귀 최적화(TCO)를 지원해서 일반 재귀에 비해 더 많은 장점을 누릴 수 있어요.

 

결론은 스위프트 컴파일러인 LLVM이 꼬리재귀 최적화를 지원하고, 이 덕분에 스위프트에서는 꼬리재귀를 사용했을 때 일반 재귀에 비해 여러 장점을 누릴 수 있어요.