ruby - 如何检测递归数组和哈希？

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