通过lambda定义的递归函数

Question

是否有一种使用lambda语法来定义递归constexpr函数的方便方法？我找到了一种不方便的方法，通过分配给一个constexpr函数指针来完成这个任务，但是我想要一种通过更少的输入和不改变lambda的类型来完成这个任务的方法。

用普通的方式来构造递归函数是非常简单的。特别是，自C++11以来一直支持使用单个表达式(可能包含三元操作符)。

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

不太清楚如何使用lambda语法来做到这一点。下面我将包括我的各种失败尝试，但是我找到了一种方法，使用一个constexpr函数指针而不是auto作为我正在使用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会接受这一点，GCC 9.2也会接受这一点。

// 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);
}

并运行它：

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

本节只是一个附录，解释为什么我决定使用函数指针而不是其他东西。

试图通过lambda生成递归constexpr函数的尝试失败。

1)使用auto

正如在这个有点老的问题上所解释的，使用在lambda中定义的东西的名称是允许的，但不能与类型推断很好地交互。使用std::function建议的答案

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

错误：

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

2)使用std::function。

这不起作用，因为std::function是一种非文字类型。很明显。

// 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);
}

错误消息失败：

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...)>

Answer 1

有一个技巧是由佩德罗·梅伦德斯的博客文章造成的，它绕过了直接递归，并且可以在一个constexpr上下文中使用。谢谢@HolbyBlackCat的参考文献和这个想法。

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);
};

在GodBolt上看。

(外部) lambda是一种“闭包类型”，它变成了“文字”，并且只在constexpr中使用C++17 (所以这不适用于C++14)。

PS -我稍微简化了你的阶乘函数，并且使用整数，因为IMHO --双数的使用只是分散了问题的注意力。