如何正确实现此JavaScript(TypeScript)树递归函数

Question

我正试图编写一个递归函数，但我很吃力，我希望有人能帮助我朝着正确的方向前进。我相信这将被视为"；树递归"；。

这是一个微不足道的例子来说明数据和我试图做的事情。显然，真实的数据更复杂。。。

基本上，我从一个包含单个对象数组的数组开始，如下所示，其中任何对象中的prop2都可以是有效字符串或空字符串。。。

[
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
]

我的算法需要查看上面的数组并对对象进行迭代。一旦它在prop2中遇到一个带有空字符串的对象，它就需要克隆该数组三次，并用三个不同的值(一个/两个/三个(替换该对象中的空字符串，如下所示。。。

[
[
{ prop1: "abc", prop2: "one" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
],
[
{ prop1: "abc", prop2: "two" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
],
[
{ prop1: "abc", prop2: "three" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
]

然后算法再次开始，只是输入是包含三个数组的新数组。

因此，在第二次迭代中，三个数组中的每一个都将被克隆三次，空字符串将以相同的方式被替换。

这个简单示例的最终结果将是一个由九个数组组成的数组。

如果数组中有更多具有空prop2值的对象，则会有更多的迭代。

基本上，我拿的是一组物体，其中一些道具是空的绳子和"；扩展"；该特定的prop值对应于"1"的每个排列；一个"/"两个"/"三个"；

我知道这是递归的一个理想问题，但我很难理解代码。

我认为；基本情况"；可能是我有一个对象数组，并且没有一个对象的属性为空字符串。该情况将返回该数组。

我不知道除了用三个新创建的变体调用同一个函数三次之外，其他情况会是什么样子。我也不知道这个案子会有什么结果。

我很难在网上找到与我尝试做的类似的参考示例

EDIT：看看递归响应，尽管它们都有效，但很明显，递归解决方案并不像我想象的那么简单。非递归答案实际上是最好的答案。

Answer 1

我建议这个非封闭的解决方案，它满足您的最终结果要求：

const myTree = [
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
];
let nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
while(nodesWithEmptyStrings.length > 0) {
nodesWithEmptyStrings.forEach(n => {
const firstEmptyStringLeaveIndex = n.findIndex(l=> l.prop2==="");
n[firstEmptyStringLeaveIndex].prop2 = "one";
const copy1 = JSON.parse(JSON.stringify(n));
copy1[firstEmptyStringLeaveIndex].prop2 = "two";
myTree.push(copy1);

const copy2 = JSON.parse(JSON.stringify(n));
copy2[firstEmptyStringLeaveIndex].prop2 = "three";
myTree.push(copy2);
});
nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
}
document.getElementById('result').innerText = JSON.stringify(myTree, null, 2);

<pre id="result"></pre>

Answer 2

是的，您可以使用递归来实现这一点。基本原理是修改数组，然后检查是否需要对其进行更多修改，如果是这样，则返回用新数组调用函数的结果。

这里有一个例子：

const fillers = ['one', 'two', 'three'];
const propToCheck = 'prop2';
function recursion(arr) {
const mod = arr.reduce((a, c) => {
const found = c.find(v => !v[propToCheck]);
if (found) {
const tmp = c.filter(v => v !== found);
return [...a, ...fillers.map(filler => [...tmp, { ...found, [propToCheck]: filler }])];
}
return [...a, c];
}, []);
const notDone = mod.some(v => v.some(o => !o[propToCheck]))
if (notDone) {
return recursion(mod);
}
return mod;
}
const result = recursion([
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
]);
console.log(result);

Answer 3

我不知道这是否是一个直觉上我想用递归来解决的问题，但这个将替换和检查空字符串的键作为参数的通用函数会起作用(使用带有大量析构函数的es6+语法和功能(：

const substitute = (data, index, keyToCheck, substitutes) => {
const indexOfObjectWithEmptyKeyToCheck = data[index].findIndex(obj => obj[keyToCheck] === "")
if(indexOfObjectWithEmptyKeyToCheck === -1) {
if(index === data.length - 1)
return data
else
return substitute(data, index + 1, keyToCheck, substitutes)
}
else {
return substitute(
[
...data.slice(0, index),
...(substitutes.map(
substitute => [
...data[index].slice(0, indexOfObjectWithEmptyKeyToCheck),
{ ...data[index][indexOfObjectWithEmptyKeyToCheck], [keyToCheck]: substitute },
...data[index].slice(indexOfObjectWithEmptyKeyToCheck + 1)
]
)),
...data.slice(index + 1)
],
index,
keyToCheck,
substitutes
)
}
}

const SUBSTITUTES = ["one", "two", "three"];
const result = substitute(
[
[
{ prop1: "abc", prop2: "" },
{ prop1: "def", prop2: "one" },
{ prop1: "ghi", prop2: "" }
]
],
0, 
"prop2", 
SUBSTITUTES
)
console.log(result)
console.log("Size of result: " + result.length)

基本上，我们遍历数组，只有在当前数组没有要检查的键为空字符串的对象时才递增索引，否则我们会根据需要进行替换，并在同一索引上递归。基本情况是当要检查的键不是空字符串并且索引是输入数组的最后一个索引时。

我留给你的Typescript部分是一个练习，因为我不认为键入输入数据是这里的大问题。