21. 递归 Lambda：C++14 中的泛型 Lambda 实现递归

递归，说白了就是函数调用自己。这在普通函数里很自然，但到了 Lambda 这儿，事情就变得有点微妙了。我记得第一次在项目里试图写一个递归 Lambda 时，编译器直接给我甩了一脸错误——"变量 'f' 在初始化之前无法使用"。嗯，这确实是个坑。

为什么 Lambda 不能直接递归？

先看一个最简单的例子。假设我们要写一个计算阶乘的递归 Lambda：

auto factorial = [](int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);  // 编译错误！
};

为什么会报错？因为 Lambda 表达式在定义时，右侧的 factorial 变量还没完全构造好。你想想看，编译器看到 auto factorial = ... 时，它需要先知道 factorial 的类型，才能去解析 Lambda 体里的 factorial 调用。这就成了「先有鸡还是先有蛋」的问题。

我当年刚接触 Lambda 时，第一反应是「用 std::function 包一层不就行了？」确实可以，但代价不小。

方案一：std::function 包装（C++11 可用）

#include <functional>

std::function<int(int)> factorial = [&](int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
};

// 使用
int result = factorial(5);  // 120

这里的关键是 [&] 捕获了外部的 factorial 引用。因为 std::function 是个类型擦除的包装器，它的构造在赋值语句完成时就结束了，所以 Lambda 体里可以安全地引用它。

注意：这种方式有性能开销。每次递归调用都要经过 std::function 的虚函数派发，比直接函数调用慢不少。我在一个高频交易系统的回测模块里用过这种写法，结果性能瓶颈就卡在这里——递归深度一上来，延迟直接翻倍。

方案二：C++14 泛型 Lambda + 自传递参数

C++14 引入了泛型 Lambda，也就是可以用 auto 作为参数类型。这给了我们一个更优雅的解法：把 Lambda 自己作为参数传进去。

auto factorial = [](auto&& self, int n) -> int {
    return n <= 1 ? 1 : n * self(self, n - 1);
};

// 调用时要把自己传进去
int result = factorial(factorial, 5);  // 120

这个写法有点绕，但核心思想很简单：Lambda 的第一个参数接收自身，然后在递归时把 self 再次传给自己。说白了，就是「手动实现递归闭包」。

我个人习惯把这种模式叫做「Y 组合子的 C++ 亲戚」。虽然名字吓人，但实际用起来就两行代码的事。

方案三：Y 组合子封装（推荐）

每次调用都要传自己，太丑了。我们可以封装一个工具函数，把「自传递」的逻辑藏起来：

#include <functional>

template <typename F>
auto y_combinator(F f) {
    return [f](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}

// 使用
auto factorial = y_combinator([](auto&& self, int n) -> int {
    return n <= 1 ? 1 : n * self(self, n - 1);
});

int result = factorial(5);  // 120，现在不用传自己了

这个 y_combinator 把「传自己」这一步自动化了。你只需要写递归逻辑，剩下的交给模板搞定。

小技巧：如果你觉得 self(self, ...) 的写法太丑，可以用 auto&& self 配合 decltype 做一层转发。我在一个开源项目里见过有人用宏包装，但说实话，宏的调试体验太差了，不推荐。

方案四：C++23 的 Deducing This（前瞻）

C++23 引入了一个新特性叫「Deducing This」，允许 Lambda 显式声明 this 参数。这样一来，递归 Lambda 可以写成：

auto factorial = [](this auto&& self, int n) -> int {
    return n <= 1 ? 1 : n * self(n - 1);
};

int result = factorial(5);  // 120，最自然的写法

注意看，这里的 self 不再需要手动传递了，编译器会自动处理。这是目前最优雅的递归 Lambda 写法，可惜需要 C++23 编译器支持。

知识体系总览

下面这张图总结了递归 Lambda 的几种实现方式及其适用场景：

递归 Lambda 实现方案对比 递归 Lambda std::function 包装 C++11 可用 有虚函数开销 适合简单场景 自传递参数 C++14 泛型 Lambda 调用需传自身 零额外开销 Y 组合子封装 C++14 模板 调用最自然 推荐生产使用 Deducing This C++23 新特性 最优雅，但编译器支持有限

避坑指南

我曾经在一个项目里用 std::function 方案写了一个深度优先搜索的递归 Lambda，结果递归深度到了 1000 层时，程序直接栈溢出了。排查了半天才发现，std::function 的每次递归调用都会在堆上分配内存，加上栈帧本身，内存消耗比普通递归函数大了好几倍。

所以我的建议是：

  • 性能敏感场景：用 Y 组合子或自传递参数方案，零额外开销
  • 快速原型：std::function 方案够用，但注意递归深度
  • 新项目：如果编译器支持 C++23，直接用 Deducing This
核心要点：递归 Lambda 的本质是「在 Lambda 体内引用自身」。C++14 的泛型 Lambda 通过自传递参数实现了零开销的递归，而 Y 组合子封装则让调用语法变得自然。记住，std::function 虽然方便，但性能上要打个折扣。

嗯，递归 Lambda 这个话题就聊到这儿。下次你在代码里遇到需要递归的 Lambda 场景，应该知道怎么选了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →