Problem with Ruby recursive lambda call

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?

---

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.

---

Another way to make recursive lambdas:

fac = lambda{|n, &context| n.zero? ? 1 : n * eval("fac.call(#{n-1}) {}",context.binding)}

But have to be called with empty block though

fac.call(2){} = 2
fac.call(3){} = 6
fac.call(4){} = 24

binding is used to evaluate the code outside of lambda scope