前言lambda 是 C11 引入的匿名函数对象写起来比函数对象类轻便得多。但它有一个天然的缺口lambda 没有办法在自己的函数体里调用自己。因为在 lambda 的定义处这个闭包对象还没有名字捕获列表也捕获不到一个尚未完成类型推导的变量。于是「用 lambda 写递归」成了很多人第一次尝试就卡住的地方。常见的绕过办法是先把 lambda 装进std::function再以引用方式捕获这个std::function变量。这种写法能跑但引入了类型擦除、可能的动态分配而且一旦把 lambda 返回出去捕获的引用立刻悬垂。另一条路是把「自己」作为第一个参数显式传进去让递归调用变成self(...)这样就不需要捕获任何东西。本文讲的 Y 函数Y combinator 的实用变体就是把第二种思路封装起来调用者仍然写普通的 lambda只是多一个self参数由一个小的类模板负责把*this喂进去。需要说明的是无类型 lambda 演算里的 Y 组合子依赖按名调用call-by-name而 C 是及早求值所以这里实现的是「自应用」版本语义上等价于求不动点但不是逐字照搬演算里的那个表达式。一、问题出在哪lambda 没有自己的名字先看一段很多人写过的代码// 适用于 C17这段代码无法通过编译仅用于说明问题#include iostreamint main() {auto fact [](int n) - int {return n 1 ? 1 : n * fact(n - 1); // 错误fact 在此处尚不可见};std::cout fact(5) \n;}编译器在这里报的是「未声明的标识符」。原因不在语法而在语义顺序auto fact ...的初始化表达式必须先求值完毕fact的类型才能确定而在初始化表达式内部fact还没有被声明。即便写成捕获列表[fact]捕获的也是一个类型尚未确定的实体同样不成立。把 lambda 先声明成std::function可以打破这个循环// 适用于 C17#include functional#include iostreamint main() {std::functionint(int) fact; // 先有类型后有实体fact [fact](int n) - int {return n 1 ? 1 : n * fact(n - 1);};std::cout fact(5) \n; // 按标准语义应当是 120return 0;}这段代码是合法的但代价不小每次递归调用都要经过std::function的间接调用类型擦除让内联几乎不可能fact本身是一个有状态的闭包生命周期必须覆盖所有递归调用如果把这个 lambda 返回给调用者捕获的fact引用就悬垂了。二、自应用让 lambda 把自己当参数真正干净的思路是不捕获自己而是把自己作为参数传进去。// 适用于 C17auto fact [](auto self, int n) - int {return n 1 ? 1 : n * self(self, n - 1);};调用时要写fact(fact, 5)——第一个参数是 lambda 自己。这样 lambda 内部不需要知道任何外部名字也就没有捕获、没有生命周期问题。但它仍然有两个毛病调用点很别扭泛型 lambda 的auto self让每一层都重复写self(self, ...)。Y 函数做的事情就是把这个「自我传递」的过程藏起来让调用者写fact(5)而不是fact(fact, 5)。三、Y 类的实现// 适用于 C17#include type_traits#include utilitytemplate typename Fstruct Y {F f;template typename... Argsdecltype(auto) operator()(Args... args) const {// 把 *this 作为「自己」传给 lambda 的首个参数return f(*this, std::forwardArgs(args)...);}};template typename FYstd::decay_tF make_y(F f) {return Ystd::decay_tF{std::forwardF(f)};}逐行看几个关键点F f;按值存储 lambda。用std::decay_tF是为了在make_y收到左值时退化成值类型避免Y内部存一个可能悬垂的引用。operator()是成员模板参数包Args...保证任意个数、任意类型的实参都能原样转发且不产生多余拷贝。函数体里f(*this, ...)*this的类型是const Ylambda 的auto self会推导成const Y随后self(...)又调用回这个成员模板——递归就这样闭合了。返回类型用decltype(auto)而不是auto是为了在 lambda 返回引用时保留引用语义如果确定只返回值写auto也可以。const限定要求被包装的 lambda 的operator()是 const——默认 lambda 满足这一点mutablelambda 不满足这一点后面会讲。使用时// 适用于 C17#include iostreamint main() {auto fact make_y([](auto self, int n) - int {return n 1 ? 1 : n * self(n - 1);});auto fib make_y([](auto self, int n) - long long {return n 2 ? n : self(n - 1) self(n - 2);});std::cout fact(5) \n; // 按定义应当是 120std::cout fib(10) \n; // 按定义应当是 55return 0;}注意 lambda 的返回类型必须显式写出来或者保证所有return语句类型一致且可推导。因为self的调用出现在 lambda 自己的函数体内返回类型推导时不能再回头依赖自身写成显式的- int最稳妥。四、它为什么能工作类型层面的推演make_y返回的是YLambda其中Lambda是编译器为那个 lambda 生成的唯一类类型。YLambda::operator()int被实例化时函数体是f(*this, 5)也就是调用Lambda::operator()const YLambda, int。这个 lambda 的operator()本身是模板因为参数是auto它的实例化又会调用self(n - 1)也就是YLambda::operator()int——正是最开始那个实例化。类型在这里形成了闭环但没有无限展开每一层递归复用同一个已实例化的函数运行时只是普通的函数调用。这也是它比std::function版本快的原因在开启优化时没有类型擦除没有间接跳转表lambda 的调用对编译器是可见的通常可以被内联。需要提醒的是这不是「零开销」的绝对保证——递归调用本身能否内联取决于优化器和递归深度不要把它当成性能承诺。一个容易忽略的代价是代码体积每个不同的 lambda 都会实例化一份YLambda如果程序里有几十个这样的递归 lambda目标文件会相应变大。这是模板的常规取舍不是缺陷。五、典型应用递归遍历树结构Y 函数最适合的场景是「结构递归」——对树、链表、JSON 节点这类自相似结构做遍历逻辑短、写一次就够不值得单独定义一个类。// 适用于 C17#include iostream#include memory#include string#include vectorstruct Node {std::string name;std::vectorstd::unique_ptrNode children;};int main() {auto root std::make_uniqueNode();root-name root;root-children.push_back(std::make_uniqueNode());root-children.back()-name a;root-children.push_back(std::make_uniqueNode());root-children.back()-name b;root-children.back()-children.push_back(std::make_uniqueNode());root-children.back()-children.back()-name b1;auto print make_y([](auto self, const Node* node, int depth) - void {if (node nullptr) return;std::cout std::string(static_caststd::size_t(depth) * 2, ) node-name \n;for (const auto child : node-children) {self(child.get(), depth 1);}});print(root.get(), 0);return 0;}这里传的是裸指针const Node*因为树的所有权明确在unique_ptr手里遍历只借用不拥有。这比传引用更灵活——空树可以直接用nullptr表示不用额外的std::optional。六、与其它写法的对比写法是否需要额外类型运行时开销能否返回出去适用场景std::function 引用捕获需要类型擦除、间接调用不能引用会悬垂快速原型、回调注册显式self(self, ...)不需要无额外开销可以一次性调用Y 类模板需要一个make_y无类型擦除可内联可以反复使用的递归逻辑具名函数 / 函数对象需要无可以逻辑复杂、需要重载选择的标准很简单如果递归只在一个地方用一次直接写self(self, ...)就够了如果要复用、要当参数传给别的算法或者希望调用点干净用 Y 类如果递归逻辑很复杂、需要重载或偏特化老老实实写一个具名函数或函数对象可读性反而更好。常见坑点1. 在 lambda 体内直接写自己的名字❌auto f [](int n) { return n ? n * f(n - 1) : 1; };✅auto f make_y([](auto self, int n) - int { return n ? n * self(n - 1) : 1; });f在初始化表达式里尚未声明捕获也捕获不到。这不是编译器缺陷而是名字查找顺序的必然结果。2.std::function按值捕获自身❌std::functionint(int) f [f](int n) { return n ? n * f(n - 1) : 1; };✅ 先声明再赋值并用[f]捕获或者直接用 Y 类按值捕获时捕获的是构造过程中尚未完成初始化的对象标准并不保证得到你想要的那份闭包。用引用捕获则要求f的生命周期覆盖所有调用。3.make_y不用std::decay_t❌template typename F YF make_y(F f) { return YF{std::forwardF(f)}; }✅template typename F Ystd::decay_tF make_y(F f) { ... }传左值时F被推导成TYT里存的是引用实参一销毁就悬垂。std::decay_t把引用和 cv 限定去掉保证按值持有。4. 给mutablelambda 套 Y❌auto f make_y([count 0](auto self, int n) mutable - int { ... });✅ 把可变状态放到外部或者给Y::operator()提供非 const 重载并相应调整Y::operator()是 const 成员函数内部的f也是 const调用mutablelambda 的非 constoperator()会编译失败。这不是运行时问题而是编译期就挡住的。5. 返回类型推导不出来❌auto f make_y([](auto self, int n) { return n ? n * self(n - 1) : 1; });✅auto f make_y([](auto self, int n) - int { return n ? n * self(n - 1) : 1; });lambda 的返回类型推导需要看到函数体里所有return语句而self(n - 1)的类型又依赖 lambda 自身的返回类型。显式写出返回类型循环就被切断了。6. 递归太深导致栈溢出❌ 用 Y 写的递归去处理十万层的链表 ✅ 改成迭代或者显式维护一个栈递归深度受线程栈大小限制超出后是栈溢出不是标准意义上的可捕获异常。这类问题与 Y 无关但用 lambda 写递归时更容易忽略「深度」这个维度。7. 忘记self是引用误以为能改外部状态❌ 在 lambda 里写self something;试图替换自己 ✅ 需要共享状态时显式捕获一个指针或std::shared_ptr到状态对象self是Y对象本身的引用赋值会破坏f成员行为不可预期。共享状态应当通过明确的捕获表达而不是靠修改self。总结要点说明根本问题lambda 在定义处没有名字无法直接自调用核心手法把「自己」作为首个参数传入由Y负责喂*this类型闭环YF::operator()调用F::operator()后者再调回前者值语义make_y用std::decay_t避免存悬垂引用返回类型显式写出避免推导时依赖自身开销无类型擦除优化开启时通常可内联但会为每个 lambda 生成一份实例适用场景树/链表遍历、一次性递归逻辑、需要把递归函数当值传递Y 函数的价值不在于它有多复杂而在于它把一个语言层面的限制lambda 无法自引用用类型系统干净地绕了过去。理解它的关键是看清「类型闭环」这四个字递归不是靠名字而是靠模板实例化把同一个类型反复喂给自己。真正写代码时如果只需要递归一次显式的self(self, ...)更直白只有在需要复用、需要干净的调用点时才值得引入这一层封装。