Ruby: Standard recursion patterns

Question

One of the things I commonly get hooked up on in ruby is recursion patterns. For example, suppose I have an array, and that may contain arrays as elements to an unlimited depth. So, for example:

my_array = [1, [2, 3, [4, 5, [6, 7]]]]

I'd like to create a method which can flatten the array into [1, 2, 3, 4, 5, 6, 7].

I'm aware that .flatten would do the job, but this problem is meant as an example of recursion issues I regularly run into - and as such I'm trying to find a more reusable solution.

In short - I'm guessing there's a standard pattern for this sort of thing, but I can't come up with anything particularly elegant. Any ideas appreciated

tokland · Accepted Answer · 2015-09-21T21:13:10.920

5

Recursion is a method, it does not depend on the language. You write the algorithm with two kind of cases in mind: the ones that call the function again (recursion cases) and the ones that break it (base cases). For example, to do a recursive flatten in Ruby:

class Array
  def deep_flatten
    flat_map do |item|
      if item.is_a?(Array)
        item.deep_flatten
      else
        [item]
      end
    end
  end
end 

[[[1]], [2, 3], [4, 5, [[6]], 7]].deep_flatten
#=> [1, 2, 3, 4, 5, 6, 7]

Does this help? anyway, a useful pattern shown here is that when you are using recusion on arrays, you usually need flat_map (the functional alternative to each + concat/push).

edited Sep 21 '15 at 21:13

answered May 21 '12 at 07:43

tokland

66,169
13
144
170

Thanks for the response. I was originally trying with a function outside of a class, which wouldn't recursively call item.my_flatten...but this works. Cheers – PlankTon May 21 '12 at 07:53
1

@PlankTon. Writing my_flatten as a function requires just some minor changes on the code above. But being a OOP language, and `my_flatten` a generic algorithm, it makes to sense to add it to Array. – tokland May 21 '12 at 08:07

peter · Answer 2 · 2012-05-21T07:49:34.533

4

Well, if you know a bit of C , you just have to visit the docs and click the ruby function to get the C source and it is all there..

http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-flatten

And for this case, here is a Ruby implementation

def flatten values, level=-1
  flat = []
  values.each do |value|
    if level != 0 && value.kind_of?(Array)
      flat.concat(flatten(value, level-1))
    else
      flat << value
    end
  end
  flat
end

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7]

edited May 21 '12 at 07:49

answered May 21 '12 at 07:43

peter

41,770
5
64
108

Ahh - concat. I was trying to recursively call the function itself, but that'll do it. Cheers – PlankTon May 21 '12 at 07:55

score 2 · Answer 3 · edited May 23 '17 at 10:29

Here's an example of a flatten that's written in a tail recursive style.

class Array

  # Monkeypatching the flatten class
  def flatten(new_arr = [])
    self.each do |el|
      if el.is_a?(Array)
        el.flatten(new_arr)
      else
        new_arr << el
      end
    end

    new_arr
  end
end

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7]

ruby

Although it looks like ruby isn't always optimized for tail recursion: Does ruby perform tail call optimization?

Ruby: Standard recursion patterns

3 Answers3