Dan Rubio Dan Rubio - 5 months ago 9
Ruby Question

How to return an array with cumulative values in a recursive method

I am attempting to take two values

times
and
number
and return an array of
number
repeated
times
times. Here is an example:

replicate(3, 5) # => [5, 5, 5]


Here is my attempt 1:

@array = []

def replicate(times, number)
return [] if times <= 0
@array << number
replicate(times - 1, number)
@array
end


When I run each test case once in isolation, I pass everything. However, when I run them all at once, it fails;
@array
contains all the values for every test case and
@array
will look like this at the end of the entire test suite:

@array # => [5, 5, 5, 1, 1, 1, 1, 2, 2]


Here is implementation two:

def replicate(times, number)
return [] if times <= 0
array = []
array << number
replicate(times - 1, number)
array
end


This will return only one value because recursion will create a local copy for every run.

How can I return an array that will make the test cases pass? I can't use global or instance variables, or a local copy of an array. Is there something I can use in between?

Answer

In this case there's no need to keep an accumulator either as an instance variable or an argument. All you need to do is concatenate the result from this call (which will be an array with a single element, i.e. [ number ]) with the result of subsequent calls:

def replicate(times, number)
  return [] if times <= 0
  [ number ] + replicate(times - 1, number)
end

If you wanted to use an accumulator, you could do it this way:

def replicate(times, number, accum=[])
  return accum if times <= 0
  replicate(times - 1, number, accum + [ number ])
end

(Note that you could use accum << number as well, but personally I prefer to treat data structures as immutable when writing recursive functions—because, well, it's a capital-F function and functions shouldn't have side-effects.)