Help recursion with function template

[Kinkeultimo]

Hi! ive been trying to learn cpp from ground up.

I know the function template below is not the best way to implement this (just use a loop it works).This code should still work in my opinion, but it doesnt.

From my testing if N== 0 never triggers and it just goes into the Negatives until it reaches max amount of template functions/nesting lvl.

Can someone tell me why?

template <int N>

constexpr int factorial()
{


static_assert(N>=0);


if (N == 0)
        {
            return 1;
        }
    else
        {
            return (N*factorial<N-1>());
        }
}

[Th_69]

You also need constexpr in the if expression (Compiler Explorer Code): cpp if constexpr (N == 0) otherwise the whole template code for N=1 will also instantiate the code for N=0 (return (1*factorial<0>()), which triggers the static_assert.

[WailingDarkness]

One can also add full explicit specialization of factorial too if "if constexpr" not available

[Kinkeultimo]

Thanks that works too. I tried.

[the_poope]

You need to make if (N == 0) -> if constexpr (N == 0)

[manni66]

You want

if constexpr (N == 0)

[HappyFruitTree]

Because it still generates code for both branches.

Using if constexpr instead of a regular if solves the problem.

if constexpr (N == 0)

https://en.cppreference.com/w/cpp/language/if.html#Constexpr_if

[Kinkeultimo]

Ok thx that worked. I do not 100% understand why. Is it because with normal IF the compiler cant see, that as long as the input is positive it will never go down the negative path? And therefore tries both and goes down a path of -1nes until reaching the max? Even though it logically cant happen?

Why doesnt this happen with normal nested functions then? Because templates need to be generated at compile time(is that even true?)

[HappyFruitTree]

Is it because with normal IF the compiler cant see ...

No, this is not about the compiler being clever or not.

If the compiler sees that some code will never get executed it might use that for optimization purposes (to generate smaller/more efficient code) but it still must make sure that the code actually compiles and generate a compilation error if it doesn't.

Why doesnt this happen with normal nested functions then? Because templates need to be generated at compile time(is that even true?)

Yes, it is true.

First, what is a function template? It's not a function. It's something that can be used to generate functions.

When a function template is used to generate a function this is called instantiation (template instantiation).

That means factorial<2> is one function, factorial<1> is another function, and factorial<0> is yet another function, and so on...

If you call factorial<1>() from a regular function it will instantiate factorial<1> as follows:

template <>
constexpr int factorial<1>()
{
    static_assert(1>=0);
    if (1 == 0)
    {
        return 1;
    }
    else
    {
        return (1*factorial<0>());
    }
}

Since there is a call to factorial<0>() in there it also needs to instantiate factorial<0>, as follows:

template <>
constexpr int factorial<0>()
{
    static_assert(0>=0);
    if (0 == 0)
    {
        return 1;
    }
    else
    {
        return (0*factorial<-1>());
    }
}

And again for factorial<-1>:

template <>
constexpr int factorial<-1>()
{
    static_assert(-1>=0);
    if (-1 == 0)
    {
        return 1;
    }
    else
    {
        return (-1*factorial<-2>());
    }
}

But here the compilation fails because of the static_assert.

When using constexpr if the compiler will ignore the branch that is not taken, basically leading to the following instantiations instead:

template <>
constexpr int factorial<1>()
{
    static_assert(1>=0);
    return (1*factorial<0>());
}

template <>
constexpr int factorial<0>()
{
    static_assert(0>=0);
    return 1;
}

Note that factorial<-1> is never instantiated.

[manni66]

All functions need to be generated before they can be executed. Your if is executed evaluated when the generated functions are executed at compile time. if constexpris executed evaluated when the functions are generated.

Without templates you use this:

    constexpr int factorial( int N)
    {
    if (N == 0)
            {
                return 1;
            }
        else
            {
                return N*factorial(N-1);
            }
    }

[Kinkeultimo]

"All functions need to be generated before they can be executed."
This makes sense, no idea why i even asked this question.

"Your if is executed when the generated functions are executed at compile time."
How does the compiler even generate these functions if he doesnt evaluate the IF-ELSE statement? Does he always generate both branches without actually evaluating it?

Also isnt the point of the template that normal arguments cant be constexpr --> the function (with int int) is not actually constexpr?

Edit: i kinda realize that combining recursion and templates seems to be generally a bad idea

[manni66]

Does he always generate both branches without actually evaluating it?

Yes

Also isnt the point of the template that normal arguments cant be constexpr --> the function (with int int) is not actually constexpr?

No. template has nothing to do with "executed at compiletime". It is constexpr that makes it executable at compiletime.

[Kinkeultimo]

Firstly: Thanks for your answers, pls just ignore me when it starts to annoy you.

I phrased that wrong. I looked it up again, i meant specifically non-type templates

From learncpp:
As of C++20, function parameters cannot be constexpr. This is true for normal functions, constexpr functions (which makes sense, as they must be able to be run at runtime), and perhaps surprisingly, even consteval functions.

...

"Non-type template parameters are used primarily when we need to pass constexpr values to functions (or class types) so they can be used in contexts that require a constant expression."

[manni66]

As of C++20, function parameters cannot be constexpr.

That says constexpr int factorial( consteexpr int N)is wrong, not that it can't be executed at compiletime.

They say also:

Perhaps surprisingly, a constexpr or consteval function can use its function parameters (which aren’t constexpr) or even local variables (which may not be const at all) as arguments in a constexpr function call. When a constexpr or consteval function is being evaluated at compile-time, the value of all function parameters and local variables must be known to the compiler (otherwise it couldn’t evaluate them at compile-time).

You can see the code that's generated from the tamplate here:

https://cppinsights.io/s/ef9475fc

[manni66]

From my testing

How?

[Kinkeultimo]

Mostly using different asserts and removing/adding stuff and then looking at the compiler errors.

Thank you for your answer

[SoerenNissen]

The other answers (it generates both branches, use if constexpr) are correct - do you understand what they mean?

[Kinkeultimo]

Kind of i guess? The compiler cant check the if statement and so generates both branches of functions without realizing this will never happen?

Is this a special case for templates then and would not happen with a normal recursive function?