I'm trying to understand the difference in memory use between a recursive algorithm that passes subarrays and one that passes indices to the same array, specifically with reference to Ruby's handling of memory. I've struggled to find documentation on how Ruby subarrays work in that level of detail.
E.g. in a binary search, your recursive function could look like this:
def search(list, target, low, high)
where high and low are indices, and in the method body a line that looks like this:
if list[mid_index] < target
return search(list, target, mid_index + 1, high)
Here we are always passing the same list from method to method.
Alternatively, the same code could be written as:
def search(list, target)
...
if list[mid_index] < target
return search(list[(mid_index + 1)..list.length - 1], target)
In the second case it looks like I'm passing a subset of an array (just references to the same objects?), but am I actually creating copies of the list, either by using the [] operator, or by using them as method arguments?
I've struggled to find documentation on how Ruby subarrays work in that level of detail.
I think the documentation of Array#[] is pretty clear (bold emphasis mine):
ary[start, length]→new_aryornil
The form of Array#[] that takes a start and end index (as well as the form that takes a Range) return a new array, not some sort of slice or view data type that shares the underlying array. (Although note that, of course, any implementation is allowed to perform such an optimization under the hood as long as it does not change any observable properties of the program.)