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

Answer 1

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).

Answer 2

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] 

Answer 3

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?