C++ lambda表达式实现递归的方法（附带实例）

C++ 中的 lambda 实际上是未命名的函数对象，这意味着我们可以递归地调用它。

为了演示如何编写递归 lambda，我们将考虑著名的 Fibonacci 函数示例，它通常在 C++ 中递归地实现，具体如下：

constexpr int fib(int const n)
{
    return n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
}

以这个实现为起点，我们来看看如何使用递归 lambda 重写它。

C++ lambda表达式的递归实现

要编写递归lambda函数，必须执行以下操作：

在函数作用域中定义 lambda；
将 lambda 分配给 std::function 包装器；
通过 lambda 中的引用捕获 std::function 对象，以便递归地调用它。

以下是递归 lambda 的示例：
1) 在函数作用域中调用一个递归的 Fibonacci lambda 表达式：

void sample()
{
    std::function<int(int const)> lfib =
    [&]fib(int const n)
    {
        return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
    };
    auto f10 = lfib(10);
}

2) 由函数返回的递归 Fibonacci lambda 表达式可以从任何作用域调用：

std::function<int(int const)> fib_create()
{
    std::function<int(int const)> f = [](int const n)
    {
        std::function<int(int const)> lfib = [&fib](int n)
        {
            return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
        };
        return lfib(n);
    };
    return f;
}

void sample()
{
    auto lfib = fib_create();
    auto f10 = lfib(10);
}

C++ 递归lambda的工作原理

在编写递归 lambda 表达式时需要考虑的第一件事是，lambda 表达式是一个函数对象，为了从 lambda 的主体递归地调用它，lambda 必须捕获其闭包（即 lambda 的实例化）。

换句话说，lambda 必须捕获自身，这有几个含义：
1) 首先，lambda 必须有一个名称，以便再次调用它，我们无法捕获未命名的 lambda。

2) 其次，lambda 只能在函数作用域中定义。这样做的原因是 lambda 只能从函数作用域捕获变量，它无法捕获具有静态存储周期的变量。

在命名空间作用域中或使用 static 或 external 说明符定义的对象具有静态存储周期，如果 lambda 是在命名空间作用域中定义的，则其闭包将具有静态存储周期，因此 lambda 不能捕获它。

3) 再次，lambda 闭包的类型不能保持未指定的状态，也就是说，它不能用 auto 标识符声明。

使用 auto 类型标识符声明的变量不能出现在其自己的初始化列表中，这是因为在处理初始化列表时，变量的类型是未知的。因此，必须指定 lambda 闭包的类型，我们可以通过通用函数包装器 std::function 来实现这一点。

4) 最后，不得不提的是，必须通过引用捕获 lambda 闭包。

如果我们通过复制（或按值）捕获，则会生成函数包装器的副本，但捕获完成时包装器未初始化，我们最终得到一个无法调用的对象。虽然编译器接受按值捕获，但在调用闭包时，会抛出 std::bad_function_call 异常。

在本文的第一个示例中，递归 lambda 在另一个名为 sample() 的函数中定义。lambda 表达式的签名和主体与常规递归函数 fib() 的签名和主体相同。lambda 闭包被分配给名为 lfib 的函数包装器（该包装器由 lambda 通过引用捕获），并从它的主体递归地调用它。由于闭包是通过引用捕获的，因此将在必须从 lambda 的主体调用闭包时初始化闭包。

在第二个示例中，我们定义了一个函数，该函数返回 lambda 表达式的闭包，该闭包又用 lambda 的参数定义并调用递归 lambda。当需要从函数返回递归 lambda 时，必须实现此模式，这是必要的，因为在调用递归 lambda 时，lambda 闭包必须仍然可用。如果在此之前它被销毁，就会留下一个悬空引用，调用它将导致程序异常终止。

下面的例子说明了这种错误情况：

// this implementation of fib_create is faulty
std::function<int(int const)> fib_create()
{
    std::function<int(int const)> lfib = [&lfib](int const n)
    {
        return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
    };
    return lfib;
}
void sample()
{
    auto lfib = fib_create();
    auto f10 = lfib(10);    // crash
}

解决这个问题的方法是创建两个嵌套的 lambda 表达式。fib_create() 方法返回一个函数包装器，当调用该包装器时，它将创建捕获自身的递归 lambda。这与前一个示例中所示的实现有着本质的区别。外部 lambda 不捕获任何东西，特别是不通过引用捕获，因此，不会有悬空引用这个问题。但是，当被调用时，它会创建嵌套 lambda（这是我们真正要调用的实际 lambda 的闭包），并将返回的结果作为递归 lfib lambda 的参数。

C++ lambda表达式实现递归的方法（附带实例）

C++ lambda表达式的递归实现

C++ 递归lambda的工作原理

相关文章