如何检测递归数组和散列？

Question

如何检测,其中包括一个递归结构如数组或哈希a,b和c下面？

• 最简单的递归数组实例

  a = []
  a[0] = a
  a # => [[...]]
  

• 递归周期/深度不是一个

  b = [[], :foo]
  b[0][0] = b
  b # => [[[...]], :foo]
  

• 非根级别的递归

  c = [a, :foo]
  c # => [[...], :foo]
  

Answer 1

我喜欢递归。

这是一个不错的方法，遍历所有内容并保留您看到的对象的散列（用于快速查找）

class Object
  def is_recursive?(known = {})
    false
  end
end

module Enumerable
  def is_recursive?(known = {})
    return true if known.include?(self)
    known[self] = true
    begin
      any? do |*args|
        args.any?{|item| item.is_recursive?(known)}
      end
    ensure
      known[self] = false
    end
  end
end

x = []; x << x
p x.is_recursive? # => true
p ({x => 42}).is_recursive? # => true
p [{foo: x}].is_recursive? # => true
p [[[[[[:foo], {bar: [42]}]]]]].is_recursive? # => false

请注意，这有点粗糙，您可能会遇到麻烦。例如，您将使用 无限循环[1..Float::INFINITY].is_recursive?，尽管这很容易挽救

class Range
  def is_recursive?(known = {})
    false # optimization
  end
end