C++经常使用却不知道的东西----Y组合子语法(力扣常见)

前言

• Y组合子语法，当我听到这个名词的时候我也被这个名称有点吃惊到，但是了解过后，发现他经常在刷力扣中使用;
• 这篇文章很短，但是在力扣用到的方法，注意点，差不多都总结了；
• 欢迎收藏 + 关注，本人将会持续更新。

什么是Y组合子呢？

📘 Y组合子语法是C++函数式编程的一个概念，它允许匿名函数调用自己，从而实现递归，而在C++中Lamdba式定义的就是匿名函数，所以Y组合子语法也经常和Lamdba一起使用。

🎟 在刷力扣的时候，我学到一种写法可以很方便的定义递归函数，如下实现一个二叉树的后序遍历：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        
        auto&& dfs = [&](auto&& dfs, TreeNode* root, vector<int>& res) {
            if(root == nullptr) return;
            dfs(dfs, root->left, res);
            dfs(dfs, root->right, res);
            res.push_back(root->val);
        };

        dfs(dfs, root, res);

        return res;

    }
};

我当时在力扣上看到这种写法，第一感觉就是很nb，后面也经常使用这种方法去写简单的递归， 但是也一直没有探究这种写法的具体是属于什么语法？？后面看到了一篇文章C++Y组合子才知道这种写法叫做Y组合子，所以这里进行讲解。

问题引出

🐇 这里首先用Lamdba表达式写一个斐波那契额数列求和递归：

auto fbi = [&](int n) -> int {
	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	return fbi(n - 1) + fbi(n - 2);
	};

🔬 这个问题进行运行，会发现报错：

上面意思就是：

• Lamdba表达式中无法访问fbi这个函数；
• 使用auto类型声明的变量，不能在他初始化中使用。

问题解决

👁 我们继续分析：

//上面代码分为两部分：
//第一部分
auto fbi

// 第二部分
[&](int n) -> int {
	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	return fbi(n - 1) + fbi(n - 2);
};

Lamdba是匿名函数，auto fbi定义的也是一个匿名函数，所以，他说找不到这个变量，且auto变量初始化中不能使用其定义的变量， 那怎么解决呢？？

他报错的核心就是，找不到fbi这个函数，那我们就将auto换掉，在STL库中，有一个叫做函数包装器的东西，他可以将所有函数进行打包，进而提供同一类型，改进代码如下：

std::function<int(int)> fbi = [&](int n) -> int {
	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	return fbi(n - 1) + fbi(n - 2);
	};

std::cout << fbi(10) << std::endl;

⛑ 结果：

==其他解决方法：==他说找不到fbi，那我们可以将这个Lamdba匿名函数作为参数传递过去，修改代码如下：

auto fbi = [&](auto&& self,int n) -> int {
	if (n == 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	return self(self, n - 1) + self(self, n - 2);
	};

🚻 结果如下：

这样也就完美解决了✌️✌️✌️✌️✌️✌️✌️✌️✌️
这就是Y组合子语法的使用了。