Ruby递归lambda调用的问题(Problem with Ruby recursive lambda call)

Ruby递归lambda调用的问题(Problem with Ruby recursive lambda call)

我有以下代码正确遍历图中的所有节点，如下所示：

seen = {} dfs = lambda do |node| return if seen[node] seen[node] = true $edges[node].each {|n| dfs.call n} end dfs.call 0

但是，我想这样写，我理解是正确的：

$edges[node].each &dfs

但是，当我这样做时，似乎只在$edge[node]中的节点列表的第一个元素上调用dfs 。 是什么赋予了？

I have the following code that correctly traverses all the nodes in a graph like so:

seen = {} dfs = lambda do |node| return if seen[node] seen[node] = true $edges[node].each {|n| dfs.call n} end dfs.call 0

However, I would like to write it this way, which I understand is correct:

$edges[node].each &dfs

However, when I do this it appears that dfs is only being called on the first element of the list of nodes in $edge[node]. What gives?

最满意答案

令人惊讶的是，你的问题不在于递归！ 它实际上是因为$nodes[node].each &dfs中的所有调用之间共享的集合。

让我们来看看操作：对$nodes[node].first的调用不应该有任何问题，因为我们知道代码片段适用于任何一个节点。 但是有一个问题： seen不到重置，你已经去了下一个节点！ 您已经看到了所有节点，因此当您在下一个周期中尝试一个节点时，由于条件的原因，它会立即返回到proc。 循环遍历$nodes ，每个其他调用都会发生相同的情况。 似乎只有对其余节点的调用才发生！

为了解决你的问题， dfs每次调用dfs的范围，我们仍然可以在函数式编程中做到：

dfs = lambda do |node| seen = [] sub_dfs = lambda do |sub_node| return if seen.include? sub_node seen << sub_node $edges[sub_node].each &sub_dfs end sub_dfs.call node end $edges[some_node].each &dfs

现在seen在每次调用dfs时都被安全隔离。

Surprisingly enough, your problem is not in the recursion! It actually is because of the shared seen collection among all calls in $nodes[node].each &dfs.

Let's go through the operation: the call to $nodes[node].first should not have any problems, because we know the snippet works for any one node. There is a problem however: seen is not reset, and you are already going to the next node! You already saw all the nodes, so when you try even one on the next cycle, it will immediately return out of the proc because of the condition. The same will happen for every other call as you loop through $nodes. It only seems that the calls to the rest of the nodes never happened!

To solve your problem, isolate seen to the scope of each call of dfs, which we can still do in functional programming:

dfs = lambda do |node| seen = [] sub_dfs = lambda do |sub_node| return if seen.include? sub_node seen << sub_node $edges[sub_node].each &sub_dfs end sub_dfs.call node end $edges[some_node].each &dfs

Now seen is safely isolated in each call to dfs.