递归算法中的返回值，而无需使用全局变量

Question

编写算法，该算法返回特定activity的name。

在我们的功能中，我们获得了activity的值，如果它存在于我们的数组中，则返回name的值：

示例：

findMatch('scuba diving', activityItems) = 'Beach'
const activityItems = [
    {
        name: 'Sunday',
        items: [
            {
                name: 'Gym',
                activity: 'weights',
            },
        ],
    },
    {
        name: 'Monday',
        items: [
            {
                name: 'Track',
                activity: 'race',
            },
            {
                name: 'Work',
                activity: 'meeting',
            },
            {
                name: 'Swim',
                items: [
                    {
                        name: 'Beach',
                        activity: 'scuba diving',
                    },
                    {
                        name: 'Pool',
                        activity: 'back stroke',
                    },
                ],
            },
        ],    
    },
    {} ...
    {} ...
];

我的实现：

let match = '';
const findMatch = (activity, activityItems) => {
    for (let i = 0; i < activityItems.length; i += 1) {
        if (activityItems[i].activity === activity) {
            match = activityItems[i].name;
            return match;
        }
        if (activityItems[i].items && findMatch(activity, activityItems[i].items)) {
            return match;
        }
    }
    return false;
};

但是，由于使用全局变量，我不喜欢我的实现。有没有办法在没有它的情况下返回正确的值？

我尝试了以下操作：

const findMatch = (activity, activityItems) => {
    for (let i = 0; i < activityItems.length; i += 1) {
        if (activityItems[i].activity === activity) {
            return activityItems[i].name;              
        }
        if (activityItems[i].items) {
            return findMatch(activity, activityItems[i].items);
        }
    }
    return false;
};

，但这总是返回错误或未定义的。

有什么建议？

Answer 1

为什么首先将该全局变量保留？只需返回名称，如果存在，则返回null。将递归搜索的结果保留在A local 变量中，仅在不是null时返回的结果：

const findMatch = (activity, activityItems) => {
    for (let i = 0; i < activityItems.length; i++) {
        if (activityItems[i].activity === activity)
            return activityItems[i].name;
        if (activityItems[i].items) {
            let match = findMatch(activity, activityItems[i].items);
            if (match) return match;
        }
    }
    return null;
};

Answer 2

当找不到值时，内置的 Array.prototype.find方法返回 undefined，所以我将使用 undefined作为无匹配结果遵循该示例。

我也会在实现您的功能时使用for of。

const activityItems = [
  {name: 'Sunday',items: [{name: 'Gym',activity: 'weights'}]},
  {name: 'Monday',items: [{name: 'Track',activity: 'race'},
      {name: 'Work',activity: 'meeting'},
      {name: 'Swim',items: [{name: 'Beach',activity: 'scuba diving'},
          {name: 'Pool',activity: 'back stroke'}]}]},
  {},
  {}
];
const findMatch = (needle, haystack) => {
  for (let {activity, name, items} of haystack) {
    if (activity == needle) return name;
    if (items && (items = findMatch(needle, items))) return items;
  }
  return undefined;
}
console.log(findMatch('scuba diving', activityItems))

这还使用for of循环中的破坏性调解来获取所需的特定属性。我重复使用items变量，以分配递归调用的结果。您不需要这样做，但是它使它短一点，而不必仅出于此目的声明变量。

---

这是一个使用.reduce()来帮助满足衬里的版本，但是现在我们丢失了短路： - （。

const activityItems = [
  {name: 'Sunday',items: [{name: 'Gym',activity: 'weights'}]},
  {name: 'Monday',items: [{name: 'Track',activity: 'race'},
      {name: 'Work',activity: 'meeting'},
      {name: 'Swim',items: [{name: 'Beach',activity: 'scuba diving'},
          {name: 'Pool',activity: 'back stroke'}]}]},
  {},
  {}
];
const findMatch = (needle, haystack) => {
  return haystack.reduce((res, {activity, name, items}) =>
    res !== undefined ? res :
    activity == needle ? name :
    items && findMatch(needle, items)
  , undefined)
}
console.log(findMatch('scuba diving', activityItems))

---

另外一个版本，使用功能技术，无需内置方法。如果功能编码是您所追求的，我会采用这种方法。

const activityItems = [
  {name: 'Sunday',items: [{name: 'Gym',activity: 'weights'}]},
  {name: 'Monday',items: [{name: 'Track',activity: 'race'},
      {name: 'Work',activity: 'meeting'},
      {name: 'Swim',items: [{name: 'Beach',activity: 'scuba diving'},
          {name: 'Pool',activity: 'back stroke'}]}]},
  {},
  {}
];
const findMatch = (needle, haystack) => {
  if (!haystack || !haystack.length) {
    return undefined;
  }
  const {activity, name, items} = haystack[0];
  return activity == needle ? name :
         findMatch(needle, items) || findMatch(needle, haystack.slice(1));
}
console.log(findMatch('scuba diving', activityItems))

---

好，再一次。这是最后一个的小变化。由于我们谈论使用尾部递归的纯粹功能编程，因此定义将头部与尾部分开的参数很有用。 spread语法和 ret rest语法使它变得容易。

const activityItems = [
  {name: 'Sunday',items: [{name: 'Gym',activity: 'weights'}]},
  {name: 'Monday',items: [{name: 'Track',activity: 'race'},
      {name: 'Work',activity: 'meeting'},
      {name: 'Swim',items: [{name: 'Beach',activity: 'scuba diving'},
          {name: 'Pool',activity: 'back stroke'}]}]},
  {},
  {}
];
const findMatch = (needle, head, ...tail) => {
  if (!head) {
    return undefined;
  }
  const {activity, name, items} = head;
  return activity == needle ? name :
         items && findMatch(needle, ...items) || findMatch(needle, ...tail);
}
console.log(findMatch('scuba diving', ...activityItems))