최적화, Tail Recursion

Recursion

Recursion / 재귀 문법은 다양한 문제를 간단하게 해결할수 있는 방법 중 하나입니다.

특히 Backtracking과 Dynamic programming에서는 빠지지 않는 요소 중 하나입니다.

재귀와 공간복잡도

간단한 재귀의 예시를 하나 들어보겠습니다.

아래 코드는 팩토리얼을 구하는 코드입니다.

def normal(i):
    if i <= 1: return 1
    return i * normal(i-1)
    

위 함수를 normal(4)와 같이 호출시

4 * normal(3) 을 리턴 하는 함수
3 * normal(2) 를 리턴 하는 함수
2 * normal(1) 을 리턴 하는 함수
1 을 리턴하는 함수

와 같이 총 4개의 함수가 사용되며 각 함수의 주소는 시스템 스택에 저장됩니다.

즉 무조건 N개의 주소가 스택에 저장되어야 하기에 공간복잡도는 O(N) 이 되는 것입니다.

각각의 함수는 자신의 값을 리턴하고 나면 시스탬 스택으로부터 pop 되겠지만,
4 * normal(3)의 경우는 normal(3)이 끝날때까지 4와 곱하는 연산을 할수 없기 때문에
꼼짝없이 연산이 끝나기만을 기다리며 시스템 스택에서 기다리고 있여야 한다는 것입니다.

그러면 이걸 방지할수 있는 방법이 있을까요?

Tail Recursion

Tail recursion은 컴파일러의 최적화를 이용해 위 계산을 공간복잡도 O(1)에 해결할수 있는 방법입니다.

코드는 아래와 같습니다.

def tail(i, val=1):
    if i <= 1: return val
    return tail(i-1, val * i)

다른점은 일단 패러미터에 val값이 생겼다는 것이며 리턴시 따로 계산이 없다는 것입니다.

이 함수를 tail(4) 와 같이 호출 할 시

tail(3, 1 * 4) 를 리턴하는 함수
tail(2, 1 * 4 * 3) 를 리턴하는 함수
1 * 4 * 3 * 2 를 리턴하는 함수

총 3개의 함수가 있게 됩니다.

그런데 생각해 보면 tail(3, 1*4)를 리턴하는 함수에 대해, 리턴시 따로 계산이 없어 기다릴 필요가 없게 됩니다.

즉 컴파일러 단에서 본 함수는 시스템 스택에서 pop 해버리고 tail(3, 1*4)를 호출 한 뒤 바로 리턴 해 버리면 되는 것입니다.

이게 계속 반복되면 결국 1 4 3 * 2를 리턴하는 함수만 시스템 스택에 남게 되고, 이로 인해 공간 복잡도는 O(1)이 됩니다.

허나 이는 분명히 컴파일러 단에서 일어나는 과정이기에 컴파일러가 이를 지원하지 않는다면 공간복잡도는 여전히 O(N) 이 될 것입니다.

지원 하는 컴파일러 및 언어

참조 : https://en.wikipedia.org/wiki/Tail_call#Language_support

언어	지원 여부
자바스크립트	ES6 부터 지원
Golang	지원하지 않음
Kotlin	tailrec 으로 지원