constexpr recursive function defined via lambda

Question

Is there a convenient way to define a recursive constexpr function by using the lambda syntax? I found an inconvenient way to do it by assigning to a constexpr function pointer, but I'd like a way to do this with less typing and without changing the type of the lambda.

Making a recursive constexpr function in the ordinary way is pretty straightforward. In particular, using a single expression, possibly containing ternary operators has been supported since C++11.

constexpr double factorial2(double x) {
    return (x < 0) ? 0 : \
           (x == 0) ? 1 : \
           /*otherwise*/ (x * factorial2(-1 + x));
}

It is less clear how to do this using the lambda syntax. I'll include my various failed attempts below, but I found a way to make a constexpr function by using a constexpr function pointer instead of auto as the type annotation for the variable I'm intializing with my lambda.

typedef double (* factorial_t)(double);

constexpr factorial_t factorial = [](double x) constexpr noexcept -> double {
    return (x < 0) ? 0 : \
           (x == 0) ? 1 : \
           /*otherwise*/ (x * factorial(-1 + x));
};

Clang will accept this, and so will GCC 9.2 on godbolt.

// foo.cpp
#include <cstdio>

typedef double (* factorial_t)(double);

constexpr factorial_t factorial = [](double x) constexpr noexcept -> double {
    return (x < 0) ? 0 : \
           (x == 0) ? 1 : \
           /*otherwise*/ (x * factorial(-1 + x));
};


int main() {
    constexpr auto x{factorial(27)};
    printf("%f\n", x);
}

And running it:

$ rm -f ./a.out && clang++-7 -std=c++17 foo.cpp && ./a.out
10888869450418351940239884288.000000

This section is just an appendix explaining why I decided to use a function pointer rather than something else.

Failed attempts to produce a recursive constexpr function via lambda.

1) using auto

As explained in this somewhat old question, using the name of the thing you're defining inside the lambda is allowed, but doesn't interact well with type inference. The answers suggested using std::function

auto factorial = [](double x) constexpr noexcept -> double {
    return (x < 0) ? 0 : \
           (x == 0) ? 1 : \
           /*otherwise*/ (x * factorial(-1 + x));
};

error:

bar.cpp:7:31: error: variable 'factorial' declared with deduced type 'auto' cannot appear in its own initializer
           /*otherwise*/ (x * factorial(-1 + x));

2) using std::function.

This doesn't work because a std::function is a non-literal type. Apparently.

// bar.cpp
#include <cstdio>
#include <functional>

constexpr std::function<double(double)> factorial = [](double x) constexpr noexcept -> double {
    return (x < 0) ? 0 : \
           (x == 0) ? 1 : \
           /*otherwise*/ (x * factorial(-1 + x));
};


int main() {
    constexpr auto x{factorial(27)};
    printf("%f\n", x);
}

Fails with the error message:

bar.cpp:5:41: error: constexpr variable cannot have non-literal type 'const std::function<double (double)>'
constexpr std::function<double(double)> factorial = [](double x) constexpr noexcept -> double {
                                        ^
    /usr/bin/../lib/gcc/aarch64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/functional:1834:11: note: 'function<double (double)>' is
          not literal because it is not an aggregate and has no constexpr constructors other than copy or move constructors
        class function<_Res(_ArgTypes...)>

This looks promising: https://stackoverflow.com/a/40873505/2752075 — HolyBlackCat, Dec 29 '19 at 23:09
@HolyBlackCat: Dirty trick... will it work in a constexpr context? — einpoklum, Dec 29 '19 at 23:13

einpoklum · Accepted Answer · 2019-12-30T12:07:01.737

There's a trick due to a blog post by Pedro Melendez, which circumvents direct recursion, and can be used in a constexpr context. Thanks @HolbyBlackCat for the reference and the idea.

constexpr auto factorial = [](int n) {
    auto factorial_impl = [](int n, auto& factorial_ref) {
        if(n <= 1) { return 1; }
        return n * factorial_ref(n-1, factorial_ref);
    };
    return factorial_impl(n,factorial_impl);
};

See it on GodBolt.

The (external) lambda is a "closure type", which became "literal" and usable with constexpr only in C++17 (so this won't work with C++14).

PS - I simplified your factorial function a bit and am using integers because IMHO the use of doubles just distracts from what the question is about.

constexpr recursive function defined via lambda

1 Answers1