前言
众所周知，C++11起出现了 lambda表达式 ，用于创建一个闭包，使得C++函数式编程的实现更为容易。本文不对lambda表达式的历史意义以及工程意义做过多探讨，只是给大家介绍一下如何递归调用lambda表达式。关于lambda表达式的基本用法，敬请移步 cppreference或相关博客，本文默认读者具有最基本的lambda语法认识。
前置知识
阅读本文，你需要有：
- 相当基本的C++语法基础
- 十分基本的C++ lambda表达式语法基础
- 非常基本的递归函数认识
- 最为基本的中文基础
我们知道，倘若直接如同普通函数一般在函数体内尝试递归调用是会语法错误的，无论是采用引用捕获亦或是值捕获都无法完成，此处不做赘述。因此我们需要借助别的东西来实现递归调用。
C++11，借助std::function
以斐波那契数列为例，我们可以使用lambda表达式来构造一个 std::function 对象，如同这样：
#include <iostream>
#include <functional>
int main(int argc, char* argv[])
{
std::function<int(int)> fib = [&fib](int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); };
std::cout << fib(5);
return 0;
}
不过很显然，这种方法从声明形式上来看并不是那么优雅，从书写形式上来看，右边lambda写了一遍的函数签名左边还要照抄一遍，过于繁琐与丑陋。此外，用闭包去初始化std::function对象，本质上并没有解决lambda递归调用的问题，只是规避了这个问题而已，反而引入了许多新的问题，它并不是零开销抽象的。另外他还有一些功能上的残缺，比如我们尝试实现一个尾递归调用的斐波那契数列：
很显然，对于带有默认参数的lambda表达式，std::function并不能承载其全部功能。
C++14，基于Y不动点组合子（Y Combinator）
如果读者有基本的lambda演算基础，应该对于“Y不动点组合子”有一些概念，它是用来解决匿名函数的递归调用问题的。
科里化
具体理论此处不做讲述，直接看代码，相对纯正的FP写法如下，由于我们要做科里化，传递lambda表达式，此处使用了来自C++14的泛型lambda，即支持在lambda表达式的参数列表中使用auto：
#include <iostream>
int main() {
auto T = [&](auto x) { return [&](auto y) { return y([&](auto z) {return x(x)(y)(z); }); }; };
auto X = T(T);
auto fib = X([](auto f) { return [&](auto n)->int { return n < 2 ? n : f(n - 1) + f(n - 2); }; });
std::cout << fib(5);
return 0;
}
直接传入(刷力扣常用)
这样看起来比较繁琐，我们可以这样简化（就我的个人习惯而言，在LeetCode刷题时采用的是这种形式）：
#include <iostream>
int main(int argc, char* argv[])
{
auto fib = [](auto&& self, int n, int i = 0, int num1 = 0, int num2 = 1) {
if (i >= n) return num1;
else return self(self, n, i + 1, num2, num1 + num2);
};
std::cout << fib(fib, 5);
return 0;
}
打包
区别于使用科里化构造一个构造器，我们这里直接选择接受一个lambda表达式作为参数调用，缺点是每次调用的时候需要将自己传进去，比较麻烦，因此我们直接使用另一个lambda或者std::bind打包一下就行了：
#include <iostream>
int main(int argc, char* argv[])
{
auto f = [](auto&& self, int n, int i = 0, int num1 = 0, int num2 = 1) {
if (i >= n) return num1;
else return self(self, n, i + 1, num2, num1 + num2);
};
auto fib = [&f](int n) { return f(f, n); };
std::cout << fib(5);
return 0;
}
不过这样实际上有一点不好，就是我们只需要一个fib，但是却多出来了一个f，污染了命名空间，那么如何解决呢？比较容易想到的是直接定义在fib的函数体内部：
#include <iostream>
int main(int argc, char* argv[])
{
auto fib = [](int n) {
auto f = [](auto&& self, int n, int i = 0, int num1 = 0, int num2 = 1) {
if (i >= n) return num1;
else return self(self, n, i + 1, num2, num1 + num2);
};
return f(f, n);
};
std::cout << fib(5);
return 0;
}
但是这样很显然，我们每调用一次fib，都要重新初始化一次f，如果不考虑编译器优化，将会有肉眼可见的性能开销，因此在这里我们可以使用同样来自C++14的带初始化器的捕获列表，这样f将只会在fib初始化时初始化：
#include <iostream>
int main(int argc, char* argv[])
{
auto fib = [
f = [](auto&& self, int n, int i = 0, int num1 = 0, int num2 = 1) {
if (i >= n) return num1;
else return self(self, n, i + 1, num2, num1 + num2);
}](int n) { return f(f, n); };
std::cout << fib(5);
return 0;
}
关于返回值推断
在最后，需要指出的一点是，注意到我在最开始是直接返回的一个三目运算符，而在此处则使用的if - else语句返回，这是为了引出一个问题，即自动推断的返回值问题。
我们将代码改为这样，可以发现发生了一个语法错误：
#include <iostream>
int main(int argc, char* argv[])
{
auto fib = [
f = [](auto&& self, int n, int i = 0, int num1 = 0, int num2 = 1) {
return i >= n ? num1 : self(self, n, i + 1, num2, num1 + num2);
}](int n) { return f(f, n); };
std::cout << fib(5);
return 0;
}
通过阅读报错可以知道，我们尝试调用self，但是我们并不知道self的返回类型。关于发生这个错误的原因，通俗来描述，就是在知道函数返回值之前便调用了这个函数。搞清楚了原因，解决起来也就很简单了，一种方法是如同上文那样，在调用前返回一个值，这样编译器就能提前推断出返回值，另一种是使用尾后返回值类型，这也是更为通用的做法：
#include <iostream>
int main(int argc, char* argv[])
{
auto fib = [
f = [](auto&& self, int n, int i = 0, int num1 = 0, int num2 = 1)->int {
return i >= n ? num1 : self(self, n, i + 1, num2, num1 + num2);
}](int n) { return f(f, n); };
std::cout << fib(5);
return 0;
}
关于std::function与自引用的性能讨论
如前文言，function不是零开销抽象的，这不仅仅是设计哲学的问题，function本身的开销其实是比较大的，在某些场景，尤其是本文讨论的用来做lambda递归的场景尤为显著，在LeetCode上甚至有的题目使用function做lambda递归无法通过，这是比较现实的问题，比如3203. 合并两棵树后的最小直径，使用以下代码勉强可以擦线通过（此代码主体来自灵神题解，我自己没有做这个题），如果别的地方常数稍微大一点很有可能就过不了了，而使用注释中的代码则可以击败百分百通过，C++的lambda本身是零开销抽象的，和裸函数性能一样，问题主要是出在function：
class Solution {
public:
int diameter(vector<vector<int>>& edges) {
vector<vector<int>> g(edges.size() + 1);
for (auto& e : edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x);
}
int res = 0;
function<int(int, int)> dfs = [&](int x, int fa) -> int {
int max_len = 0;
for (auto y : g[x]) {
if (y != fa) {
int sub_len = dfs(y, x) + 1;
res = max(res, max_len + sub_len);
max_len = max(max_len, sub_len);
}
}
return max_len;
};
// auto dfs = [&](auto&& dfs, int x, int fa) -> int {
// int max_len = 0;
// for (auto y : g[x]) {
// if (y != fa) {
// int sub_len = dfs(dfs, y, x) + 1;
// res = max(res, max_len + sub_len);
// max_len = max(max_len, sub_len);
// }
// }
// return max_len;
// };
// dfs(dfs, 0, -1);
dfs(0, -1);
return res;
}
int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
int d1 = diameter(edges1);
int d2 = diameter(edges2);
return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1});
}
};C++23 借助Deducing this实现lambda递归
实际上早在2017年的提案 P0839R0 就对于简化lambda递归做了努力，他尝试这么做：
#include <iostream>
int main(int argc, char* argv[])
{
auto fib = [] self(int n) {
if (n < 2) return n;
return self(n - 1) + self(n - 2);
};
std::cout << fib(5);
return 0;
}差不多是给lambda起个名字，然而并没有实装。。
C++23有这样一条提案：P0847R7，这条提案实际上并不是为了lambda准备的，但是lambda递归刚好可以利用上。详细内容可以自行查看，这里直接展示用法：
#include <iostream>
int main(int argc, char* argv[])
{
auto fib = [](this auto&& self, int n, int i = 0, int num1 = 0, int num2 = 1)->int {
return i >= n ? num1 : self(n, i + 1, num2, num1 + num2);
};
std::cout << fib(5);
return 0;
}
可以看到，基本语法是和上面Y不动点组合子的形式类似的，同样是第一个参数接受一个闭包对象，不过调用形式更为美观了。
借此我们可以直接一行爆栈（雾）
int main(int argc, char* argv[])
{
[](this auto f)->void { f(); }();
return 0;
}
遗憾的是目前（2022年6月24日04:09:46）为止LeetCode还没有支持。。。
特大好消息！！！！！！！近日LeetCode已支持Clang19，这个版本的Clang已实现Deducing This，现在可以用这种方法做lambda递归了！！！！
