Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can this recursive function for creating a range work?

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?

like image 804
KooiInc Avatar asked Jun 13 '11 10:06

KooiInc


2 Answers

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]
like image 191
Jeremy Avatar answered Sep 29 '22 13:09

Jeremy


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.

like image 34
Guffa Avatar answered Sep 29 '22 12:09

Guffa