[c++] Template Recursion(템플릿 재귀)

#include <iostream>

// 템플릿 재귀를 이용한 팩토리얼 계산 함수
template <int N>
struct Factorial {
    static const int value = N * Factorial<N - 1>::value;
};

// 템플릿 재귀의 기저조건(Basis case)
template <>
struct Factorial<0> {
    static const int value = 1;
};

int main() {
    const int result = Factorial<5>::value;
    std::cout << "Factorial of 5 is: " << result << std::endl;
    return 0;
}

간단한 예시이다. 간단히 구조체를 이용해서 구현할 수 있다. class를 이용해도 마찬가지로 구현할 수 있다.
탬플릿 재귀를 이용해서 다소 복잡한 함수나 클래스를 구현할 수 있다.

• 구조체 내부에서 호출하는 형태는 기존의 재귀함수 사용법이랑 유사하다. 하지만 running time에 stack에 쌓이면서 재귀적으로 실행되는 재귀함수와 달리 탬플릿 재귀는 compile 시간에 compiler가 재귀적으로 함수를 만들어낸다. 그래서 재귀를 호출을 많이 하게 된다면 컴파일 시간이 매우 길어질 수 있는 문제점이 있다. 또한 기저사례를 안 만들거나 잘못 만들면 컴파일이 무한루프가 도는 상황이 발생한다.

---

필자는 이 기능을 merge-insertion sort algorithm(Ford-Johnson algorithm) 을 c++을 통해서 작성하며 사용하였다.

해당 알고리즘에서는 정렬을 재귀적으로 호출을 하는데, 호출 시 현재 원소 값들을 두개씩 pair로 만든 다음에 호출하여 정렬하는 특징이 있다. 이를 구현하면서 큰 문제점이 있었는데, 그 것은 재귀적으로 호출하면서 해당 함수의 자료형이 바뀐다는 점이다.
Ex) int -> std::pair<int,int>
std::pair<int,int> -> std::pair<std::pair<int,int>,std::pair<int,int>>
이러한 식으로 재귀적으로 자료형이 변한다.
이를 해결하기 위해 찾은 것이 위의 템플릿 재귀이다.
단순히 함수를 이용해서 템플릿 재귀하는 법은 구글링을 해도 잘 나오지 않아서 구조체나, class를 이용해서 구현하였다.

아래는 pseudo code 이다.

template<typename T, int N>
class MergeInsertionSort
{
public:
	void sort(std::vector<T> &arr)
   {
   	// pair 생성
       
       MergeInsertionSort<std::pair<T, T>, N - 1>::sort(groups); // 재귀 호출
   
   	// MergeInsertion sort
   } 
};

// base case (기저 사례)
 template<typename T, int 0>
class MergeInsertionSort
{
	void sort(std::vector<T> &arr)
   {
   	return;
   }
};

참고로 해당 코드에서 class 생성 시 N의 값을 얼마를 주냐에 따라 정렬할 수 있는 개수에 제한이 있다. 실제로 compiler가 재귀적으로 생성된 자료형에 따라서 class를 생성하기 때문이다. 하지만 N 값을 많이 줄 수록 compile 시간이 많이 소요된다.