Is there a way to use Class Template Argument Deduction Guide recursively? (is it Turing Complete)

Question

I am playing with Class Template Deduction Guide and trying to use it recursively. But I am not able to get the following code to compile

#include <type_traits>

template<int N>
using int_const = std::integral_constant<int,N>;

template<int N>
struct Foo{
    constexpr static int value = N;

    template<int C>
    constexpr Foo(int_const<C>){};
};

Foo(int_const<0>) -> Foo<1>;

template<int N>
Foo(int_const<N>) -> Foo<N*(Foo{int_const<N-1>{}}.value)>;

int main(){
    return Foo{int_const<5>{}}.value;
}

This is the error:

<source>: In substitution of 'template<int N> Foo(int_const<N>)-> Foo<(N * >     Foo{std::integral_constant<int, (N - 1)>{}}.value)> [with int N = -894]':
<source>:17:51:   recursively required by substitution of 'template<int N> Foo(int_const<N>)-> Foo<(N * Foo{std::integral_constant<int, (N - 1)>{}}.value)> [with int N = 4]'
<source>:17:51:   required by substitution of 'template<int N> Foo(int_const<N>)-> Foo<(N * Foo{std::integral_constant<int, (N - 1)>{}}.value)> [with int N = 5]'
<source>:20:30:   required from here
<source>:17:1: fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)
 Foo(int_const<N>) -> Foo<N*(Foo{int_const<N-1>{}}.value)>;
 ^~~

compilation terminated.

Answer 1

You need a helper template:

template<int N>
struct foo_helper
{ static constexpr int value = N * Foo{int_const<N-1>{}}.value; };
template<>
struct foo_helper<0>
{ static constexpr int value = 1; };

With this (and only) deduction guide:

template<int C>
Foo(int_const<C>)
-> Foo<foo_helper<C>::value>
;

Live demo with Foo{int_const<5>{}}.value correctly evaluated to 120.

Why is so?

Because with the following deduction guide

template<int N>
Foo(int_const<N>) -> Foo<N*(Foo{int_const<N-1>{}}.value)>;

when CTAD kicks in, all guides are considered; even if you provided a more specialized guide (Foo<0>), this recursive guide is explicitly specialized and Foo{int_const<N-1>{}} eventually gets specialized for N=0, hence the infinite recursion.

The introduction of an indirection layer, foo_helper breaks this infinite recursion: you can specialize a class, not a deduction guide.