说说什么是函数式编程思维

假设来到阿里巴巴面试，面试官可能就会让你反转下二叉树镜像。请大家先思考下，怎么实现？

（1）命令式编程思维

一种实现方式是这样的：

Node invertTree(root){
 if (root is null){
   return null;
 }
  
 root.left = invertTree(root.right);
 root.right = invertTree(root.left);
  
 return root;
}

我们首先判断节点是否为空，如果为空则直接抛出；然后翻转右树放置在左边；翻转左树放置在右边。

这其实是一种命令式编程方式，即我们把要做的事情，以步骤的形式描述出来，然后交给机器去执行。

这也正是命令式编程的理论模型——图灵机的特点。一条写满数据的纸带，一条根据纸带内容运动的机器，机器的每一步都需要在纸带上写出命令。

图灵机指的是一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息（命令），然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

（2）函数式编程思维

函数式思维提供了另一种思维途径——翻转二叉树，我们可以看做是要得到一颗和原来二叉树对称的新二叉树。这颗新二叉树的特点是每一个节点都递归地和原树相反。

Node invert(node){
  if (node is null) {
      return null;
  } else {
      return new Tree(node.value, invert(node.right), invert(node.left));
  }
}

这段代码体现的思维是旧树到新树的映射。对一颗二叉树而言，它的镜像树就是左右节点递归镜像的树。

同样是翻转二叉树，但这段代码得到结果的方式和之前的命令编程模式有本质的差别：通过描述一个 旧树->新树 的映射，而不是描述「从旧树得到新树应该怎样做」来达到目的。

世界的两部分好像在照镜子，就称为镜像世界。

---

函数式编程思维：描述旧树到新树的映射关系。

命令式编程思维：描述从旧树得到新树应该怎样做。