Ruby: Standard recursion patterns
design-patterns, recursion, ruby
Solution
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`).
Problem
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