algorithm - 递归函数在结果中生成重复项

Question

我在 coffescript 中尝试了一些算法，结果得到了一些意想不到的输出。这是我的代码:

traverse = (tree, stack) ->
  stack.push tree.node
  if not tree.branches
    stack
  else
    traverse branch, stack for branch in tree.branches

one  = { node: 1 }
two  = { node: 2 }
tree = { node: "+", branches: [one, two] }

console.log traverse  one, [] # => [ 1 ]
console.log traverse  two, [] # => [ 2 ]
console.log traverse tree, [] # => [ [ '+', 1, 2 ], [ '+', 1, 2 ] ]

我希望在遍历 tree 时得到的输出是 [ '+', 1, 2 ] 但这会重复。我在这里错过了一些简单的事情吗？

谢谢。

Answer 1

如果函数没有明确的return，那么返回值就是最后一个表达式的值。函数中的最后一个表达式是这样的:

if not tree.branches
  stack
else
  traverse branch, stack for branch in tree.branches

请注意，if 和 for 都是 CoffeeScript 中的表达式。

那么 if 的值以及函数的值是多少？如果 tree.branches 存在，那么您将获得 stack，否则您将获得 for 的值。 CoffeeScript for 循环的计算结果为一个数组:

a = (i for i in [0 .. 6])
# a is now [0, 1, 2, 3, 4, 5, 6]

因此，如果 tree.branches 存在，您最终将返回一个由 transverse 返回的内容组成的数组:一个由...组成的数组的数组，其中最终数组都是堆栈。

您只需要更明确地说明您的返回值，像这样的事情应该可以解决问题:

traverse = (tree, stack) ->
  stack.push tree.node
  if tree.branches
    traverse branch, stack for branch in tree.branches
  stack # <------------ Now we always return stack

演示:http://jsfiddle.net/ambiguous/2QJ9e/