自从接触了纯函数，刷算法题刷得举步维艰。

什么是纯函数：同样的传入参数，一定可以得到相同的输出

纯函数又被称为无副作用的函数，不会改变外部的状态。

比如在 JS 中，array.slice()对数组的切片，返回的是一个新的数组，为纯函数。

相对的，array.splice()对数组的插入与删除是对于原数组操作，不是纯函数。

纯函数的意义，在于保证不会对函数外部的状态有隐式的修改。这在大型的、遍地都是状态的系统中非常重要。如果不保证纯函数，多个函数内部去修改了同一外部状态，容易出现意想不到的 Bug。

图的邻接矩阵定义

let map = {
  point: ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7'],
  side: [
    [0, 1, 0, 1, 1, 0, 0, 0],
    [1, 0, 1, 0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 0],
  ]
}

图深度遍历的非纯函数实现

// DFS 深度优先遍历，从 第 index 个节点开始. visited 记录已访问的节点，全局共用一个 visited
function DFStraverse(index: number = 0, visited = [map.point[0]]) {
  if (visited.length === map.point.length) {
    console.log(visited.toString())
    return
  }

  map.side[index].forEach((isSide, targetv) => {
    if (isSide && !visited.includes(map.point[targetv])) {
      visited.push(map.point[targetv])
      DFStraverse(targetv, visited)
    }
  })
}

以上代码的问题：

• map 定义在了外部，和别的函数共用
• visited 是全局共用同一个，但却每次都要作为参数传入，逻辑上既不合也没有必要。并且作为函数参数（而不是全局变量），每次都对 visited 作了修改。这里还好，因为要的就是修改后的 visited（实际上是全局的 visited）。但如果题目是一个回溯问题，就需要管理 visited 的状态，在修改了之后，递归出栈时还得改回来。

图深度遍历的纯函数实现

// DFS 深度优先遍历，从 第 index 个节点开始. visited 记录已访问的节点，全局共用一个 visited
// 纯函数实现
function DFStraverse(index: number, map: { point: string[], side: number[][] }) {
  const visited = [map.point[index]]

  function traverse(index: number) {
    // 终止条件
    if (visited.length === map.point.length) {
      console.log(visited.toString())
      return
    }

    map.side[index].forEach((isSide, targetv) => {
      if (isSide && !visited.includes(map.point[targetv])) {
        visited.push(map.point[targetv])
        traverse(targetv)
      }
    })
  }

  traverse(index)
}

使用闭包，把共用的 visited 固定为状态。内部再定义函数作递归。 map 也作为外层的参数传入，里面不去修改。

状态其实在各种算法里挺重要的。不少空间换时间的极限操作都要用到。

算法注定是“不纯”的，能做的也不过是用闭包来保存状态。有时候觉得，纯不纯的也没有这么重要。