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

注意ifs 和fors 都是 CoffeeScript 中的表达式。

那么它的价值是什么if，因此函数的价值是什么？如果tree.branches存在那么你得到stack，否则你得到的值for。CoffeeScriptfor循环计算为一个数组：

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

因此，如果tree.branches存在，您最终会返回一个返回的数组transverse：一个数组数组的数组 ... 其中最终的数组是 all stack。

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

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/