Как работает рекурсия времени компиляции?

Я нашел здесь код Печать от 1 до 1000 без цикла или условий

Может кто-нибудь объяснить, как работает рекурсия времени компиляции, не смог найти в гугле

// compile time recursion
template<int N> void f1()
{ 
    f1<N-1>(); 
    cout << N << '\n'; 
}

template<> void f1<1>() 
{ 
    cout << 1 << '\n'; 
}


int main()
{
    f1<1000>();
}

Спасибо!


c++ compile-time
person VextoR    schedule 11.03.2011    source источник
comment
На самом деле есть хитрость, специализация условная, правда ключевого слова if нет...   -  person Matthieu M.    schedule 11.03.2011
comment
Есть ли эмпирическое правило о том, что это намного быстрее, чем рекурсия во время выполнения?   -  person David Doria    schedule 30.01.2012
comment
В чем преимущество использования этого вместо обычной рекурсии?   -  person zzzzz    schedule 10.06.2013

Ответы (5)


arrow_upward
12
arrow_downward

Он многократно создает экземпляр шаблона f1<N> с уменьшающимися значениями для N (f1<N>() вызывает f1<N-1> и т. д.). Явная специализация для N==1 завершает рекурсию: как только N становится равным 1, компилятор выберет специализированную функцию, а не шаблонную.

f1<1000>() заставляет компилятор создавать экземпляры f1<N> 999 раз (не считая последнего вызова f1<1>). По этой причине может потребоваться некоторое время для компиляции кода, в котором интенсивно используются методы метапрограммирования шаблонов.

Все это в значительной степени зависит от навыков оптимизации компилятора - в идеале он должен полностью удалить рекурсию (которая служит только хаком для эмуляции цикла for с использованием шаблонов).

person Alexander Gessler    schedule 11.03.2011

arrow_upward
2
arrow_downward

Концептуально он работает почти так же, как рекурсия во время выполнения. f1<1000> вызывает f1<999>, а затем выводит 1000. f1<999> вызывает f1<998>, а затем выводит 999 и т. д. Как только оно достигает 1, специализация шаблона действует как базовый случай для прерывания рекурсии.

person Mark B    schedule 11.03.2011
comment
почему он печатает от 0 до 1000, а не от 1000 до 0? - person VextoR; 11.03.2011
comment
@VextoR: Это потому, что он сначала вызывает f1‹N-1›, а затем печатает. - person sharptooth; 11.03.2011
comment
@VextoR, потому что он выводит N на консоль ПОСЛЕ создания экземпляра следующего шаблона. - person Maxpm; 11.03.2011
comment
@острый зуб ‹N-1› == 999? Должен ли он печатать 999 ? - person VextoR; 11.03.2011
comment
@VextoR: Нет, сначала он вызывает f1<999>(), а затем печатает 1000. - person sharptooth; 11.03.2011

arrow_upward
1
arrow_downward

Достаточно просто, каждый экземпляр шаблона создает новую функцию с измененным параметром. Как если бы вы определили: f1_1000(), f1_999() и так далее.

Каждая функция вызывает функцию, в имени которой на 1 меньше. Поскольку существует другой шаблон, не рекурсивный, для определения f1_1() у нас также есть стоп-кейс.

person kriss    schedule 11.03.2011

arrow_upward
1
arrow_downward

Это не гарантирует чистую рекурсию времени компиляции. Компилятор должен будет создать экземпляр функции f1() для всех значений параметров от 2 до 1000, и они будут вызывать друг друга.

Тогда компилятор может увидеть, что эти вызовы можно просто превратить в последовательность операторов cout << .... Может быть, он устраняет вызовы, а может и нет — это на усмотрение компилятора. С точки зрения C++ это цепочка вызовов функций, и компилятор может делать что угодно, пока это не меняет поведение.

person sharptooth    schedule 11.03.2011

arrow_upward
1
arrow_downward

Вы объяснили расчет факториала здесь.

Кстати, обратите внимание, что ваша функция не работает для отрицательных чисел.

person BЈовић    schedule 11.03.2011