Range using recursion, how to output a new array Javascript

Question

How do you output a new array using recursion without declaring an empty array outside of the function? Another way of doing it will be creating an inner function and then return newFunction(), but it is not allowed as the task is to call the function itself. Here's what I have so far:

var newArr=[];
var range = function(x, y) {
    if(x === y-1){
        return newArr;
    }
    if(x < y){
        newArr.push(x+1);
        newArr = range(x+1,y);
    }
    else{
        newArr.push(x-1);
        newArr = range(x-1,y);
    }
    return newArr;
};
range(2,10) //[3,4,5,6,7,8,9]

Answer 1

Try this:

function rangeRecursive(start, end) {            
    if(start === end){
        return end;
    } else if(start > end){
        return [];
    } else {
        return [start].concat(rangeRecursive(++start, end));
    } 
}

console.log(rangeRecursive(4, 15));

Answer 2

There are many ways to skin this cat.

1. The simple way: create an array with the first value in it, then concatenate the remaining values to it.

var range = function(x,y){
    return x+1 >= y ? [] : [x+1].concat(range(x+1, y));
}
console.log(JSON.stringify(range(1, 10)));

The array is being constructed from right to left. Notice how the recursive call to range is not the last thing the function does before it returns: concatenation of the array follows.

2. We can also rewrite the function to be tail recursive with an accumulator as a parameter.

var range2 = function(x,y,a){
    a = a || [];
    return x+1 >= y ? a : range2(x+1, y, a.concat(x+1));
}
console.log(JSON.stringify(range2(1, 10)));

Now the call to range2 is the last thing the function does before it returns. ES6 compliant JS engines are required to optimise calls in tail position (in strict mode) by discarding the execution context from the stack.

Notice how we're now constructing the array from left to right.

3. You can avoid the extra parameter by using a helper function. I've used an inner function, but it doesn't have to be.

var range3 = function(x,y){
    var r = function(x,y,a){
        return x+1 >= y ? a : r(x+1, y, a.concat(x+1));
    }
    return r(x, y, []);
}
console.log(JSON.stringify(range3(1, 10)));

4. Tail recursive using continuation passing style.

var range4 = function(x,y){
    var r = function(x,y,c){
        return x+1 >= y ? c([]) : r(x+1, y, function(a){
            return c([x+1].concat(a));
        });
    }
    return r(x, y, function(a){return a;});
}
console.log(JSON.stringify(range4(1, 10)));

Notice the similarity with the original range: the array is constructed in reverse. This is trickier to get your head around and may be something you never need, but it doesn't hurt to be aware of it.

Answer 3

you can simply do like this;

var range = (x,y,a=[]) => (++x < y && (a = range(x,y,a.concat(x))),a),
      arr = range(2,10);
console.log(arr);

Note that the returned array is a parameter of the function and is passed to successive recursive calls.

Answer 4

So the key to this kind of thinking is understanding that you should be creating a lot of arrays.

Looking at a slightly different example...

A factorial is a number which goes backwards, through positive integers, multiplying each term with the term below it, and is written like 5!. These are helpful when you find yourself asking questions like:
"How many permutations of ____ are there?"

"Given these 5 things, how many permutations can I arrange them in, from left to right?"

5! // =>
5 x 4 x 3 x 2 x 1  // =>
120

You could see how we could build a loop and set a variable for a counter, and a variable for the total, and multiply the current total by the current value of the counter we're decrementing.

But instead of doing that, we can try to use recursion. First, think about how we could simplify that 5 x 4 x ... into one repeated step.

Really, 2! is 2 x 1. 3! is 3 x 2 x 1, which happens to be 3 x 2!.

So the general case might be something like: n! == n x (n - 1)!

So I might write a generalized function which does something like this:

// DO NOT RUN THIS FUNCTION!
function factorial (n) {
  return n * factorial(n - 1);
}

So if I run factorial(5) and use my imagination, we can see that the program is doing something like:

factorial(5)
  => return 5 * factorial(5-1)
    => return 4 * factorial(4-1)
      => return 3 * factorial(3-1)
        => ...

Can you see any problems with the function as-is?
I said at the beginning that factorials (in this simplified case) are over positive integers.

How does my function know to stop when the integers stop being positive? It doesn't, currently. Which is why the above implementation attempts to run forever, and will freeze the browser, while it tries to, until it gets thousands or tens of thousands of functions deep, before it says that you've reached the maximum depth of the call stack and explodes.

What we really need is a condition or a set of conditions, which we use to determine when we're done. This is a base-case.

if (shouldStop(n)) {
  return defaultValue;
}

Or in our case:

function factorial (n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

Now, when we run the function, we have:

factorial(5)
  => 5 * factorial(5 - 1)
    => 4 * factorial(4 - 1)
      => 3 * factorial(3 - 1)
        => 2 * factorial(2 - 1)
          => 1
        => 2 * 1
      => 3 * 2
    => 4 * 6
  => 5 * 24
=> 120

This is recursion. And because of where the call is (returned at the very end of whatever branch you're in) it's a special kind of recursion (tail recursion), which allows some languages to optimize the code, replacing the function call with the contents of the function call, and thus skip adding to the call-stack like the first version (future versions of JS will support this power).

In more modern JS, I might rewrite it to look something like

const factorial = n => n <= 1 ? 1 : factorial(n - 1);

So now, what about other cases?

Well, sometimes, you need to make sure you're passing more things in. Think about what your problem is, and what kinds of counters or flags or collectors you need, in order to do your job.

Here's one:

function makeNumberString (current, max, initialString) {
  var str = initialString || ""; // maybe I don't have one yet
  var currentString = str.concat(current.toString());

  if (current > max) {
    return initialString;
  }
  return makeNumberString(current + 1, max, currentString);
}

makeNumberString(0, 9); // "0123456789"

There are other ways of filling that function out, to make it do the same thing. Note that currentString there is always a brand new string, made by joining the string that I was given with the new value I was passed. I'm not actually modifying the original string, but creating a new copy [HINT!!].

I hope that helps you.