How to reimplement the map method in ruby using recursion?

Question

I'm a ruby newbie, learning to code. I wanted to understand how some of the methods available from the Enumerable module work. So I'm reimplementing them. One challenge was to implement them using recursion. However, I'm running into a problem when trying to implement the Enumerable#Map method using recursion.

This is my code:

class Array
  def mymap_recursive(&block)
    copy_of_array = dup
    new_array = []
    return new_array if copy_of_array.empty?
    value = copy_of_array.shift
    new_array << yield(value)
    copy_of_array.mymap_recursive(&block)
  end
end

I tried to figure out why it wasn't working so I put

puts "#{new_array}"

at the end of the method. Then in Sublime Text, I did

arr = [2,2,5,5,10]
arr.mymap_recursive {|n| n * n}

After pressing cmd+b, the output I got was:

[100]
[25]
[25]
[4]
[4]

I cannot figure out why its not returning one array with all the values.

Thanks for your help!

in line 3 you return new_array (which is []) if copy-of-array is empty. Where do you return it with something else in it? — Taryn East
– Taryn East, Commented May 6, 2015 at 2:07
To me line 3 represents the base case where the recursion should break if the condition is true. I thought it would just return a new_array with all the values in it. — zshnr
– zshnr, Commented May 6, 2015 at 2:20
Yes, that is the base case... and it will only ever return new_array with nothing in it.. because that's what it has in it after you assign [] to it... ;) you also have to have a case where you return new_array with something in it — Taryn East
– Taryn East, Commented May 6, 2015 at 6:14

tykowale · Accepted Answer · 2015-05-06 02:39:25Z

2

What is happening in your code is every time you call mymap_recursive(&block) the new_array is being lost. To solve this you must have a way to maintain the new array that is being built recursively. A simple change to your code is including new_array = [] in your method definition, then passing new array each time. Here would be the code with my changes in place:

class Array
  def mymap_recursive(new_array = [], &block)
    copy_of_array = self.dup
    return new_array if copy_of_array.empty?
    value = copy_of_array.shift
    new_array << yield(value)
    copy_of_array.mymap_recursive(new_array, &block)
  end
end

Then when you call

arr = [2,2,5,5,10]
p arr.mymap_recursive {|n| n * n}
#returns
#[4, 4, 25, 25, 100]

If you have any questions over this syntax or anything let me know and I will try my best to explain it!

answered May 6, 2015 at 2:39

tykowale

4493 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user12341234 · Accepted Answer · 2015-05-06 03:06:46Z

1

Another solution which doesn't change the method signature and doesn't mutate any data:

class Array
  def mymap_recursive(&block)
    if empty?
      []
    else
      [block.call(first)] + drop(1).mymap_recursive(&block)
    end
  end
end

answered May 6, 2015 at 3:06

user12341234

7,2836 gold badges27 silver badges52 bronze badges

2 Comments

zshnr Over a year ago

thank you so much for helping! I have a question about this method though: isn't line 6 dropping an element from the original array that the mymap method is being called on?

user12341234 Over a year ago

Yes. But it also processes the dropped element, too, before the plus sign. Line 6 performs two tasks, separated by the plus sign. Before the plus sign it takes the "first" element of the array and calls the block (in your example "n * n") on it. After the plus sign it drops the first element (the one that's already been squared), and applies this method to all the remaining elements. Then, the + operator joins both sides.

Collectives™ on Stack Overflow

How to reimplement the map method in ruby using recursion?

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related