递归Lambda：std::function实现递归、Y组合子简介

递归，说白了就是函数调用自己。这在普通函数里很自然，但到了Lambda表达式这儿，就有点绕了。为什么？因为Lambda是个匿名对象，它没有名字，怎么在自己体内调用自己？

我刚开始接触这个问题时，也卡了好一会儿。后来发现，其实有两条路可以走：一条是用std::function这个“容器”把Lambda装起来，另一条是更纯粹的Y组合子。今天咱们就把这两条路都走一遍。

为什么Lambda不能直接递归？

先看个简单的例子。你想写个Lambda计算阶乘：

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

这段代码编译不过。原因很简单：在Lambda内部，factorial这个变量还没定义完呢。你想想看，编译器解析Lambda体时，factorial还在构造中，它根本不知道factorial是什么东西。

嗯，这里要注意：Lambda的捕获列表是在定义时确定的，而不是在调用时。所以你不能在Lambda体内引用它自己——除非你用了某种“间接”的方式。

方法一：std::function + 引用捕获

最常见的做法，就是用std::function包装一下，然后通过引用捕获自己。我个人习惯用这种方式，因为它直观、好理解。

#include <iostream>
#include <functional>

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

    std::cout << factorial(5) << std::endl;  // 输出 120
    return 0;
}

关键点在于：[&]捕获了外部所有变量的引用，包括factorial本身。当Lambda体执行到factorial(n - 1)时，factorial已经是一个完整的std::function对象了，所以可以正常调用。

我曾经在项目里犯过这个错。当时写了一个递归解析JSON的Lambda，用了值捕获，结果一运行就段错误。查了半天才发现是捕获方式的问题。从那以后，我写递归Lambda时都会多看一眼捕获列表。

方法二：通过参数传递自身

还有一种技巧，就是把Lambda自己作为参数传进去。这有点像函数式编程里的“不动点”思想。

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

// 调用时要把自己传进去
std::cout << factorial(factorial, 5) << std::endl;  // 输出 120

这种写法不需要std::function，也没有额外的开销。但调用方式有点别扭——每次都要把Lambda自己作为第一个参数传进去。你想想看，这多麻烦。

不过，我们可以用一个小技巧包装一下：

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

std::cout << factorial(5) << std::endl;  // 输出 120

这样外部调用者就不需要关心内部实现了。嗯，这其实已经有点Y组合子的雏形了。

Y组合子简介

Y组合子，说白了就是一个“递归生成器”。它接受一个“不完整的函数”（即需要递归调用的函数），然后返回一个完整的递归函数。

在C++里实现Y组合子，需要用到模板和Lambda的泛型特性。我直接上代码：

#include <iostream>

template <typename F>
auto Y(F f) {
    return [f](auto... args) {
        return f(f, args...);
    };
}

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

    std::cout << factorial(5) << std::endl;  // 输出 120
    return 0;
}

这个Y函数接收一个Lambda，这个Lambda的第一个参数是“自己”，后面的参数才是真正的参数。然后Y返回一个新的Lambda，这个新Lambda隐藏了“把自己传给自己”的细节。

三种方式的对比

方法	优点	缺点	适用场景
std::function + 引用捕获	直观、易读、调用自然	有运行时开销（虚函数调用）	大多数日常场景
通过参数传递自身	无额外开销、纯Lambda	调用方式别扭、需要包装	对性能有极致要求的场景
Y组合子	纯函数式、无状态、可复用	理解门槛高、模板代码多	函数式编程风格的项目

避坑指南

我曾经在项目里用递归Lambda解析一个深层嵌套的JSON结构。一开始用的std::function方式，跑得挺好。后来数据量大了，发现性能有点慢。换成“参数传递自身”的方式后，速度提升了不少。

但要注意：递归深度太深会导致栈溢出。Lambda递归和普通函数递归一样，都有栈深度限制。如果你要处理的数据层级很深（比如超过1000层），建议改用循环或尾递归优化。

另外，std::function方式有个隐藏的坑：如果你在Lambda内部修改了捕获的std::function对象（比如重新赋值），会导致未定义行为。因为Lambda体执行时，std::function正在被调用，修改它相当于“一边开车一边换轮胎”。

知识体系图

下面这张图总结了递归Lambda的三种实现方式及其关系：

总结

递归Lambda其实不复杂。核心就一句话：让Lambda能访问到自己。用std::function是最直接的方式，用参数传递是更纯粹的方式，Y组合子则是函数式编程的终极解法。

我个人建议：日常项目用std::function就够了。如果你在写一个对性能敏感的基础库，可以考虑参数传递的方式。至于Y组合子，理解它的思想就好，不用强求在代码里用上。

嗯，递归Lambda就聊到这儿。记住一点：能用循环解决的问题，尽量别用递归。递归虽好，但栈空间有限，别把自己绕进去了。

---

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