如何递归复制数组

Question

我想递归地产生一个单位n-超立方体的顶点（点）（为了清楚起见，这里只是一个立方体）。这个想法是通过递归地遍历 x、y 和 z 分量来指定立方体的点。为什么不直接使用嵌套的 for 循环？递归本质上是赃物。这是我的功能：

var points = [];

function makeCube(d, point) {
  console.log(d,point);
  
  if(d == 0) {
    points.push(point);
  } else {
    extension1 = [...point];
    extension1.push(0);

    extension2 = [...point];
    extension2.push(1);
    
    makeCube(d - 1, extension1);
    makeCube(d - 1, extension2);
  }
}

我打电话给makeCube(3, [])。控制台显示为：

[Log] 3 – [] (0) (sketch.js, line 57)
[Log] 2 – [0] (1) (sketch.js, line 57)
[Log] 1 – [0, 0] (2) (sketch.js, line 57)
[Log] 0 – [0, 0, 0] (3) (sketch.js, line 57)
[Log] 0 – [0, 0, 1] (3) (sketch.js, line 57)
[Log] 1 – [0, 0, 1] (3) (sketch.js, line 57)
[Log] 0 – [0, 0, 1, …] (4) (sketch.js, line 57)
etc...

当d为1时，数组中应该只有2个条目，而不是3个！当 d 为 0 时，应该有 3，而不是 4。最低层的第二个数组不知何故被抬高了一层。我特意复制扩展数组而不是将它们设置为与旧数组相同，所以我不明白发生了什么。

预期的控制台输出：

[]
[0]
[0,0]
[0,0,0]
[0,0,1]
[0,1]
[0,1,0]
[0,1,1]
[1]
[1,0]
[1,0,0]
[1,0,1]
[1,1]
[1,1,0]
[1,1,1]

Answer 1

我想我解决了问题：

var points = [];

function makeCube(d, point) {
  console.log(d, JSON.stringify(point));
  
  if(d == 0) {
    points.push([...point]);
  } else {
    let extension1 = [...point];
    extension1.push(0);

    let extension2 = [...point];
    extension2.push(1);
    
    makeCube(d - 1, extension1);
    makeCube(d - 1, extension2);
  }
}

makeCube(3, [])

3 []
2 [0]
1 [0,0]
0 [0,0,0]
0 [0,0,1]
1 [0,1]
0 [0,1,0]
0 [0,1,1]
2 [1]
1 [1,0]
0 [1,0,0]
0 [1,0,1]
1 [1,1]
0 [1,1,0]
0 [1,1,1]

我刚刚添加了 let 两次（并更改了我记录的内容）。原始脚本在 window 中创建全局 extension1 和 extension2 变量。显然，全局范围引起了一些问题。

Answer 2

您可以使用生成器将副作用 console.log 移到函数之外。这也使得跳过全局 points 变量变得容易。使用 for..of 循环遍历所有点 -

function* makeCube(d, point = []) {
  yield point
  if(d == 0) return
  yield *makeCube(d - 1, [...point, 0])
  yield *makeCube(d - 1, [...point, 1])
}

for (const point of makeCube(3))
  console.log(`(${point.join(",")})`) // caller decides effect

()
(0)
(0,0)
(0,0,0)
(0,0,1)
(0,1)
(0,1,0)
(0,1,1)
(1)
(1,0)
(1,0,0)
(1,0,1)
(1,1)
(1,1,0)
(1,1,1)

或者使用Array.from将所有的点收集到一个数组中

const points = Array.from(makeCube(3))

console.log(points)

[
  [],
  [0],
  [0,0],
  [0,0,0],
  [0,0,1],
  [0,1],
  [0,1,0],
  [0,1,1],
  [1],
  [1,0],
  [1,0,0],
  [1,0,1],
  [1,1],
  [1,1,0],
  [1,1,1],
]

如果你想计算 product，我建议你写一些不同的函数 -

function* product(t, ...more) {
  if (t == null) return yield []
  for (const p of product(...more))
    for (const v of t)
      yield [v, ...p]
}

for (const p of product([0,1], [0,1], [0,1]))
  console.log(p.join(","))
  
for (const p of product(["J", "Q", "K", "A"], ['♡', '♢', '♤', '♧']))
  console.log(p.join(""))

0,0,0
1,0,0
0,1,0
1,1,0
0,0,1
1,0,1
0,1,1
1,1,1

J♡
Q♡
K♡
A♡
J♢
Q♢
K♢
A♢
J♤
Q♤
K♤
A♤
J♧
Q♧
K♧
A♧

如何递归复制数组

How to recursively copy arrays

javascript

recursion