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

Question

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

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

// 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>();
}

Спасибо!

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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