Шаблонная рекурсия

Когда я узнал, что с помощью шаблонов C++ можно еще и рекурсию организовать, некоторое время пребывал в состоянии приятного восхищения. А когда узнал, как это все просто делается, то границ моему восторгу и вовсе не было :)

Вот пример вычисления факториала с помощью шаблонов (источник - http://peter.infosreda.com/ru/2008/06/23/template_recursion):

template<int i>
struct Factorial {
 enum { value = i * Factorial<i-1>::value };
};

template<>
struct Factorial<0> {
 enum { value = 1 };
};

А вот пример использования:

unsigned int a = Factorial<10>::value;
int b = Factorial<11>::value;

Если возник вопрос, причем тут enum, ответ прост: enum компилируется всегда, даже если шаблон не инстанцирован. Поэтому даже если мы не используем шаблон, компилятор все равно проверит корректность нашего кода.

Я немножко модифицировал пример, чтобы расширить диапазон с int до long long. Правда, пришлось отказаться от enum:

template<long long i>
struct Factorial {
 const static long long value = i * Factorial<i-1>::value;
};

template<>
struct Factorial<0ll> {
 const static long long value = 1;
};

Думаю, общую идею Вы уловили: описываем в шаблоне константное рекурсивное выражение, в специализации - ограничение рекурсии.

У этого кода, конечно же, есть ряд недостатков:

• В качестве аргумента можно передавать только константные выражения
• Глубина шаблонной рекурсии ограничена. Например, мой g++ 4.4.1 ругнулся, что больше 500 глубину он инстанцировать не будет :)
• Увеличение объема бинарника (простое вычисление Factorial<20> генерирует 20 классов)
• Увеличение времени компиляции

Правда эти недостатки сглаживаются и плюсами:

• О превышении глубины рекурсии мы узнаем от компилятора явно
• О переполнении мы тоже узнаем сразу от компилятора (например, Factorial<30>::value уже не влезает в long long)
• Если мы вычислили Factorial<20>, то все меньшие значения факториала уже вычислены и все необходимые классы инстанцированы

Теперь мое личное мнение: согласен, это все попахивает извращениями, но ведь правда хороший способ весело разобраться в тонкостях работы шаблонов С++ :)