一些递归的代码例子

findxc commented 2 years ago

恩，当我需要写递归的时候，我就会从这篇笔记去 copy 然后改改 ... 所以我把这篇笔记发出来，让更多人 copy =.=

------- 下面是笔记内容 -------

如果内心有点畏惧递归，那就写它 100 次 ~

一些实际开发中的递归例子

数据格式如下。

// 组织结构树
const orgTree = [
  {
    id: 1,
    name: 'A',
    children: [
      {
        id: 2,
        name: 'A_1',
        children: [
          {
            id: 3,
            name: 'A_1_1',
          },
          {
            id: 4,
            name: 'A_1_2',
          },
        ],
      },
    ],
  },
  {
    id: 5,
    name: 'B',
    children: [
      {
        id: 6,
        name: 'B_1',
      },
      {
        id: 7,
        name: 'B_2',
      },
    ],
  },
]

// 带有用户的组织结构树
const orgWithUserTree = [
  {
    id: 1,
    name: 'A',
    type: 'org',
    children: [
      {
        id: 2,
        name: 'A_1',
        type: 'org',
        children: [
          {
            id: 3,
            name: 'A_1_1',
            type: 'org',
          },
          {
            id: 4,
            name: 'A_1_2',
            type: 'org',
            children: [
              {
                id: 1,
                name: '张三',
                type: 'user',
              },
              {
                id: 2,
                name: '李四',
                type: 'user',
              },
            ],
          },
        ],
      },
      {
        id: 3,
        name: '王五',
        type: 'user',
      },
    ],
  },
  {
    id: 5,
    name: 'B',
    type: 'org',
    children: [
      {
        id: 6,
        name: 'B_1',
        type: 'org',
        children: [
          {
            id: 4,
            name: '赵六',
            type: 'user',
          },
        ],
      },
      {
        id: 7,
        name: 'B_2',
        type: 'org',
      },
    ],
  },
]

把树形结构打平为一级

function flatten(list = []) {
  return list.reduce((total, current) => {
    const { children, ...obj } = current
    return total.concat(obj, flatten(children))
  }, [])
}

在树形结构中找到 id 为某个值的项

function findItemById(list = [], id) {
  for (const item of list) {
    if (item.id === id) {
      return item
    }
    const findChildrenResult = findItemById(item.children, id)
    if (findChildrenResult) {
      return findChildrenResult
    }
  }
  return null
}

从树形结构中解析出所有的人

function parseAllUsers(list = []) {
  return list.reduce((total, current) => {
    const { type, children, ...obj } = current
    return total.concat(type === 'user' ? obj : [], parseAllUsers(children))
  }, [])
}

只保留树形结构中的组织

function omitUsers(list = []) {
  return list
    .filter(item => item.type === 'org')
    .map(item => {
      const { children, ...obj } = item
      return {
        ...obj,
        children: omitUsers(children),
      }
    })
}

根据一个 id 返回在树中的路径

function findPathIdsById(list = [], id, pathIds = []) {
  for (const item of list) {
    const currentPathIds = pathIds.concat(item.id)
    if (item.id === id) {
      return currentPathIds
    }
    const findChildrenResult = findPathIdsById(
      item.children,
      id,
      currentPathIds
    )
    if (findChildrenResult) {
      return findChildrenResult
    }
  }
  return null
}

树相关的算法题

二叉树的最大深度

题目详见 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/ 。

解法如下。根节点的深度其实就是左子节点深度和右子节点深度取最大值然后 +1 。

var maxDepth = function (root) {
  if (!root) {
    return 0
  }
  const leftMaxDepth = maxDepth(root.left)
  const rightMaxDepth = maxDepth(root.right)
  return Math.max(leftMaxDepth, rightMaxDepth) + 1
}

二叉树中路径总和

题目详见 https://leetcode-cn.com/problems/path-sum-ii/ 。

解法如下。假设路径总和是 a ，当前根节点值是 x ，那么就是找左子节点和右子节点的路径总和为 a - x 。

var pathSum = function (root, targetSum, path = []) {
  if (!root) {
    return []
  }

  const currentPath = path.concat(root.val)
  if (!root.left && !root.right) {
    return root.val === targetSum ? [currentPath] : []
  }

  const currentSum = targetSum - root.val
  const leftNodePaths = pathSum(root.left, currentSum, currentPath)
  const rightNodePaths = pathSum(root.right, currentSum, currentPath)
  return leftNodePaths.concat(rightNodePaths)
}

调用栈溢出

写递归需要注意一点，如果数据规模比较大，可能存在调用栈溢出的问题，这时可以改用循环的方式去实现。

尾调用和尾递归优化

尾调用 - 维基百科，自由的百科全书尾调用优化 - 阮一峰的网络日志

尾调用：函数的最后一个执行语句是返回一个函数的方式。比如在一个函数中最后一条执行的语句是 return add(a, b) ，我们就是这是尾调用。

一般来说，如果在一个函数中调用了另外一个函数，那么需要将另外一个函数添加进调用栈中，如果说不断发生函数调用，那么调用栈剩余空间就会越来越少。

尾调用优化的意思是说，如果是尾调用的话，那么在调用新函数时，并不需要创建一个新的栈帧，直接在当前栈帧上继续处理即可，减少了对内存空间的消耗。

而尾递归就是指在递归中使用尾调用，这样就避免了调用栈溢出的问题。

需要注意，有些语言可能并不支持尾调用优化特性。

NemoZhong commented 2 years ago

😂😂😂666

colgin commented 2 years ago

有一段时间，我也一直处理递归问题，脑子里基本都是递归，不过我基本都可以一遍过，我总结下来就是，你要思考递归的输入和输出，理清楚递归关系就行了

findxc / blog