Geek Answers Handbook

How to define recursive arrays and hashes?

How can I detect arrays or hashes that include a recursive structure like a , b and c below?

  • The simplest instance of a recursive array

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

  • The cycle / depth of recursion is not one

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

  • Non-root Recursion

     c = [a, :foo] c # => [[...], :foo]
+6
source share
3 answers

I like recursion.

Here's a decent way, iterating through everything and saving a hash of the objects you saw (for quick searching)

 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

Remember that this is a little rude and you may run into trouble. For example, will you have endless loops with [1..Float::INFINITY].is_recursive? although this is easily possible with

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

You cannot smooth a recursive array, so you can check it out:

 begin a.flatten rescue ArgumentError => e e.to_s =~ /recursive/ end
+3
source

Are you looking for an include? method include?

 a = [] a[0] = a a.include? a => true

But this does not work for nested arrays, like your second example. You can do this recursively:

 def check_recursive(array, target = nil) target ||= array return true if array.include?(target) array.any? do |obj| if obj.kind_of? Array check_recursive(obj, target) obj.include?(target) end end end

Basically two abbreviations to find it recursive: look in depth or deep search or breadth-first search . The best solution depends on your problem. My example implements a deep frist search, which is usually a good idea.

+1
source

More articles:


All Articles