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

Я нашел здесь код Печать от 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>();
}

Спасибо!

Ответы

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

У вас есть объяснение факториала здесь.

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