Почему следующая функция не генерирует хвостовую рекурсию с Clang?
Под clang следующая функция генерирует объектный код для хвостовой рекурсивной функции:
template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
return counter >= limit
? number % limit != 0
: number % counter
? is_prime(number, number / counter, counter + 2)
: false;
}
template<typename T>
constexpr bool is_prime(T n)
{
return n == 2 || n == 3 || n == 5
? true
: n <= 1 || n % 2 == 0
? false
: is_prime(n, n / 3, T{3});
}
но изменяя одну строку (позволяя логическому результату «ненормализоваться»), он перестает генерировать хвостовой рекурсивный объектный код:
template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
return counter >= limit
? number % limit // changed here
: number % counter
? is_prime(number, number / counter, counter + 2)
: false;
}
template<typename T>
constexpr bool is_prime(T n)
{
return n == 2 || n == 3 || n == 5
? true
: n <= 1 || n % 2 == 0
? false
: is_prime(n, n / 3, T{3});
}
Это кланг не может оптимизировать его правильно или есть логическая причина для этого?
Чтобы форсировать оценку времени выполнения, x является интегральным простым временем выполнения ≥ 13 (одна рекурсия) или достаточно большое простое число constexpr, которое препятствует оценке во время компиляции из-за большой глубины рекурсии:
is_prime(x);
Решение
Если у вас есть exp1 ? exp2 : exp3, чтобы определить тип ?: Скажите тип exp3 превращается в тип exp2 (если возможно). Это означает, что вы мило BOOL результат конвертируется в тип T и должен быть преобразован обратно в bool для возврата.
Это означает, что рекурсивный вызов не является последним оператором. Я полагаю, что если вы измените порядок в тернарном операторе, вы получите хвостовой рекурсивный результат.
template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
return counter < limit
? (number % counter
? is_prime(number, number / counter, counter + 2)
: false)
: number % limit;
}
Другие решения
Других решений пока нет …