꼬리 재귀 알고리즘 (quick sort 개선)

꼬리 재귀 알고리즘을 알아보기에 앞서,
재귀 알고리즘이란 하위 문제에 대해 자신을 호출하는 알고리즘을 말한다.

 

일반적으로 유명한 예시인 factorial이 재귀로 많이 표현된다.

 

 

이렇게 재귀 호출 알고리즘은 스택 메모리 내에서 이루어지는데,
보다싶이 보조해주는 추가 공간이 O(n)만큼 필요하다보니 스택 메모리가 전부 차버리는 stack overflow가 발생할 위험이 있다.

 

그래서 이 문제를 극복하기 위해 꼬리 재귀 Tail Recursion 방법이 고안되었다.

꼬리 재귀란, 함수로부터 실행되는 재귀 호출의 그 문장이 마지막 statement에 있는 알고리즘을 말한다.

 

함수가 한번 호출되면, 스택에는 함수의 input, return, return 후 돌아갈 포인터가 저장된다.

일반적인 재귀의 경우를 보면, input과 return 후, 다시 본인을 호출했던 자리로 돌아가서 n*fac() 연산을 한다.
스택에 return 후 돌아갈 포인터가 필수적인 것이다.

하지만 꼬리 재귀의 경우를 보면 재귀 호출을 한 후에는 추가적인 연산을 요구하지 않는다.
따라서 함수의 호출을 스택에 쌓을 필요도 없고, 스택 메모리를 재사용하므로 공간 복잡도는 감소한다.

 

이렇게 꼬리 재귀를 사용해줌으로서 시간복잡도는 일반 재귀와 같지만, 공간 복잡도를 감소시켜줄 수 있다.

 

 

---

 

이번에 배운 꼬리 재귀 방식을 다른 알고리즘에 적용시킬 수 있다.

https://guhonga.tistory.com/84

Quick sort 소개

 

quick sort는 divide and conquer에서 재귀를 사용했었다.

 

quick sort의 best case와 worst case를 보면 시간과 공간 복잡도의 차이가 큰 것을 알 수 있다.

 

우리는 위와 같은 방식을 꼬리 재귀를 통해
공간복잡도를 줄임으로서 차이를 좁힐 것이다.

 

우선, 다음과 같은 코드로 quick sort의 재귀 두번을 한번으로 줄일 것이다.

 

이에 따른 알고리즘들의 스택 메모리는 다음과 같다.

 

아직 이 상태에서의 공간복잡도는 같다.

그 전에, 피봇이 정확하게 중간 지점을 잡은것이 아닌 이상 나눠진 partition들의 크기는 서로 다를텐데 어떤 하위 배열을 재귀로 선택하는 것이 좋을까?

그림을 보면 이해가 쉽겠지만 당연히 더 작은 하위 배열의 재귀가 더 적은 공간 복잡도를 갖는다.

이 상태에서의 worst case에서 스택의 깊이는 log n이다..!

아까 일반적인 quick sort의 worst case의 깊이가 n인 것에 비하면 꽤 준수해졌다.

 

 

더 작은 하위 배열을 선택하기 위해 quick sort 알고리즘을 if문을 통해 수정해주자

결과적으로 시간 복잡도는 영향을 받지 않았지만, 공간 복잡도는 worst case의 n에서 log n으로 의미 있는 수준의 성과가 있었다.