6

From the selected answer in this SO-question this very ingenious function creates an Array with a range from 1 to i:

function range1(i){return i?range1(i-1).concat(i):[]}

It works perfect. Call me stupid, but I just can't get my head around how it works. Let's say we have range1(5). Now entering the function, we have i, so it returns itself with parameter i-1 (4) and concats i (5) to it. But here I'm stuck: how does range1 know it has to do with an Array? I'd say after the first run the return value (as long as we have i, so i!==0) would be a Number. And Number has no concat method. Can someone explain this? What am I missing?

Community
  • 1
  • 1
KooiInc
  • 119,216
  • 31
  • 141
  • 177

7 Answers7

11

I've expanded this code because I find it easier to understand this way.

function range1(i){
  if (i != 0) {
     return range1(i - 1).concat(i);
  } else {
     return [];
}

The logic behind this function is that if you want the list of 3 elements (range(3)), you take the list of 2 elements (range1(i - 1)) and add 3 to the end of it .concat(i). Beyond this, you just need to handle the special case that range1(0) is the empty array [] and you're done.

Imagine a call to range1(2). Since i != 0, we get

range(2) = range(1).concat(2)

range(1) returns range(0).concat(1), giving us

range(2) = range(0).concat(1).concat(2)

Well, what is range(0)? Since i == 0, we get the empty array ([]) that we need!

range(2) = [].concat(1).concat(2) -> [1, 2]
Jeremy
  • 1
  • 85
  • 340
  • 366
  • `range(2) -> [].concat(1).concat(2) -> [1, 2]` – Guffa Jun 13 '11 at 11:09
  • +1 and thanks. Sorry I've selected Guffa's answer though; your answer explains it really well, but Guffa used a phrase that really made me understand what I missed in my thinking. – KooiInc Jun 13 '11 at 12:12
8

Now entering the function, we have i, so it returns itself with parameter i-1 (4) and concats i (5) to it.

No, it doesn't return itself. What it does is call itself, which is the recursion, then it returns the result of that call with the last element concatenated.

So, range1(5) will call range1(4), which will call range1(3), and so on. When it reaches zero it will stop making calls and just return an empty array.

range1(0) returns [], so range1(1) returns [].concat(1) which is [1], then range1(2) returns [1].concat(2) which is [1,2], and so on. When we return to range1(5) it returns [1,2,3,4].concat(5) which is [1,2,3,4,5].

Note: This function works well to create small arrays, but if you need a large array it will be a lot faster to just create the array and fill it using a regular loop.

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
2

The base case of the recursion is [], so the tail of the recursion will return an array and the other steps will concatenate to [] (and previous steps).

patapizza
  • 2,398
  • 15
  • 14
2

Let's take range1(4):

range1(4) => range1(3).concat(4)
range1(3) => range1(2).concat(3)
range1(2) => range1(1).concat(2)
range1(1) => range1(0).concat(1)
range1(0) => []

Now take the first line and replace range1(3) with its equivalent from the next line. You get this:

range1(4) => range1(2).concat(3).concat(4)

Continue replacing range1 references until there isn't any left. Final result:

range1(4) => [].concat(1).concat(2).concat(3).concat(4)
rciq
  • 1,309
  • 10
  • 10
0

The range1 function always returns an array.

It is either an an empty array (for i == 0) or a concatenated array.

Jakub Konecki
  • 45,581
  • 7
  • 87
  • 126
0

In the base case range1 returns an empty array which defines concat. As it then unwinds the numbers in the range are added to the array.

mahju
  • 1,156
  • 1
  • 14
  • 21
0

until i become 0 nothing hapens else than caling function with rediced value, but when it called with 0 it returns [] - an empty array wich in previous call aplied a concat method... it looks like range(0).concat(1) => [].concat(1) so [1] returned to previous call: [1].concat(2) and so on to begining

skazska
  • 421
  • 2
  • 8