时间戳

首页 > 解决方案 > JavaScript：在递归之间需要一个共享数组才能将结果推送到

javascript - JavaScript：在递归之间需要一个共享数组才能将结果推送到

问题描述

有一个数组，其中有一个家谱，其中有人的名字和他们的性别以及他们父母的名字（父亲和母亲）。

现在我在这里（不成功）试图列出这个家庭中一个人的所有孩子的名字：

function allChildren(parent) {
  var children = ancestors.filter(
    function(person) {
      if (parent.sex == 'm') {
        return person.father == parent.name
      } else {
        return person.mother == parent.name
      }
    }
  )
  if (children.length == 0) {
    console.log(parent.name);
  } else {
    children.forEach(allChildren);
  }
}

目前这只是控制台记录没有孩子的人。问题是，我需要将每个孩子推入一个结果数组，但我使用的是递归，所以我不能在所有递归之间共享一个结果变量。

（当然我还应该检查之前没有推送过相同的名称 - 假设没有重复 - 这不是我的问题，我知道该怎么做，我的问题是关于获得一系列结果，并填写递归步骤逐渐（每个递归步骤都可以将一个元素推入其中））。

标签： javascriptrecursiontree

解决方案

这是一种类似于 KarelG 的方法。但是，它已经足够不同了，足以保证它自己的答案。

差异

  • 这个将祖先作为参数传递，而不是将它们作为函数中的自由变量。自由变量使代码更难理解，也更难测试。

  • 它将递归函数与公共函数分开，将它们放在一个闭包中。现在人们在很多地方都在使用某种模块，这是一种不太常见的技术，但它仍然很有用，尤其是在网络上。这就是(() => {/* ... return some function */ })()语法。

  • 它使用 Set 作为递归累加器，以避免重复。

  • 它忽略了性别。我看不出检查它的理由。如果孩子说母亲是某某，我认为仔细检查 `mother.sex === 'f'` 没有任何意义。我可能在这里遗漏了一些东西。

  • 虽然它保留了提供完整人员对象并返回姓名列表的现有 API，但将其切换为仅提供姓名或返回人员列表相对容易。更多关于下面的内容。

  • 我命名它allDescendents，因为这似乎比allChildren.

代码

const allDescendents = (() => {
  const all = (family, name, children = new Set()) => {
    const kids = family.filter(p => p.father === name || p.mother === name).map(k => k.name)
    kids.forEach(kid => (children.add(kid), all(family, kid, children)))
    return children
  }
  
  return (family, person) => Array.from(all(family, person.name))
})()

const bourbons = [ // https://en.wikipedia.org/wiki/Bourbon_family_tree
  {name: 'Philip III', sex: 'm', father: 'Louis IX', mother: 'Margaret'},
  {name: 'Robert', sex: 'm', father: 'Louis IX', mother: 'Margaret'},
  {name: 'Charles', sex: 'm', father: 'Philip III', mother: '?'},
  {name: 'Louis I', sex: 'm', father: 'Robert', mother: 'Beatrice'},
  {name: 'Philip IV', sex: 'm', father: 'Charles', mother: '?'},
  {name: 'Isabella', sex: 'f', father: 'Charles', mother: '?'},
  {name: 'Peter I', sex: 'm', father: 'Louis I', mother: 'Mary'},
  {name: 'James I', sex: 'm', father: 'Louis I', mother: 'Mary'},
  {name: 'John II', sex: 'm', father: 'Philip IV', mother: '?'},
  {name: 'Peter II', sex: 'm', father: 'James I', mother: 'Jeanne'},
  {name: 'John I', sex: 'm', father: 'James I', mother: 'Jeanne'},
  {name: 'Charles V', sex: 'm', father: 'John II', mother: '?'},
  {name: 'Joanna', sex: 'f', father: 'Peter I', mother: 'Isabella'},
  {name: 'Louis II', sex: 'f', father: 'Peter I', mother: 'Isabella'},
  {name: 'James II', sex: 'm', father: 'John I', mother: 'Catherine'},
  {name: 'Louis', sex: 'm', father: 'John I', mother: 'Catherine'},
  /* .. */
]

const louis1st = bourbons[3]

console.log(allDescendents(bourbons, louis1st))

变体

考虑到这一点，使得重大改变变得相当容易。大多数这些变化也可以组合起来。

返回一个Set

Set返回 a of 值而不是a 可能更有意义Array。大概您不希望此集合包含重复项。ASet是正确的数据结构。此解决方案在Set内部使用 a，将其设为公共接口很简单。只需删除对Array.from：

-   return (family, person) => Array.from(all(family, person.name))
+   return (family, person) => all(family, person.name)

提供名称

由于您要返回一组名称，因此为输入提供名称可能会更容易。我们可以通过更改输入参数来接收名称来做到这一点：

-   return (family, person) => Array.from(all(family, person.name))
+   return (family, name) => Array.from(all(family, name))

返回人

相反，您可能更喜欢直接返回人员对象。名单只有这么有用。包含完整 Person 对象的列表可能更易于使用。这就是它的样子：

-  const all = (family, name, children = new Set()) => {
-    const kids = family.filter(p => p.father === name || p.mother === name).map(k => k.name)
+  const all = (family, person, children = new Set()) => {
+   const kids = family.filter(p => p.father === person.name || p.mother === person.name)

-  return (family, person) => Array.from(all(family, person.name))
+  return (family, person) => Array.from(all(family, person))

避免默认参数

如果函数中的默认参数困扰您（例如，编辑器中的红色波浪线），那么您可以将参数移动到导出的函数中。我喜欢将复杂性保留在一个地方，这就是为什么我在递归函数上有默认值的原因，但是有一个很好的论据可以以牺牲公共函数为代价来简化递归函数；它确实使递归函数更容易理解。

-   const all = (family, name, children = new Set()) => {
+   const all = (family, name, children) => {

-   return (family, person) => Array.from(all(family, person.name))
+   return (family, person) => Array.from(all(family, person.name, new Set()))

制作一个模块

最后，我们可以很容易地把它变成一个模块。如果您要部署到浏览器，这仍然需要一个构建步骤，但它确实简化了代码：这是一个版本：

const all = (family, name, children = new Set()) => {
  const kids = family.filter(p => p.father === name || p.mother === name).map(k => k.name)
  kids.forEach(kid => (children.add(kid), all(family, kid, children)))
  return children
}

const allDescendents = (family, person) => Array.from(all(family, person.name))

export {allDescendents}

推荐阅读