A range function in Javascript written recursively

Question

For my own learning and practice I tried to implement a function in Javascript which would populate an array with integers from 1 to the argument 'limit'. One way I did it was with a for loop:

function getRange(limit) {
    const range = [];
    for (let i = 1; i <= limit; i++) {
        range.push(i);
    }
    return range;
}

Then I wanted, again for my practice, to try and write it with a recursive function and came up with the following:

function recGetRange(limit, array) {
    const range = array || [];
    if (limit > 0) {
        range.push(limit);
        recGetRange(limit - 1, range);
    }
    return range.reverse();
}

Now both seem to work fine, but both seem also to fail when tried on large numbers. Yet the recursive option fails much earlier. I'm not exactly sure but the for loop seems to work for numbers 1E4 or 1E5 times larger at least. Am I doing something wrong here with those implementations, or is it just a dead end even trying something like that? Thanks!

In the recursive solution, you should be prepending not appending. That `reverse` will be killer. — Carcigenicate, Mar 13 '17 at 18:54
And the recursive solution will fail with a StackOverflow eventually. What does the iterative solution fail with? — Carcigenicate, Mar 13 '17 at 18:57
Yeah, I didn't think about that. unshift() seems to work for that. The recursive one fails with: RangeError: Maximum call stack size exceeded And the iterative with a longer JS Stack trace, where it says: FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory — Fuoco, Mar 13 '17 at 19:08
Ya, so the recursive solution is giving you a StackOverflow; you ran out of a stack space. There's really nothing you can do about that, especially in JS. That's just a reality when dealing with recursion. If recursion is giving you a SO, you need to either reduce the number of recurses, or make it iterative. The iterative error is just telling you the list you made took up all available memory. — Carcigenicate, Mar 13 '17 at 20:13
Thanks! So basically that would be a case where for large numbers recursive has a strong weakness in comparison to iterative. I wasn't aware that there would be such a consideration... — Fuoco, Mar 14 '17 at 08:30
Unless the language you're using can guarantee Tail Call Optimization (good to google that term), recursion will **always** fail if run long enough; just assume that. Recursion is good when the problem is inherently recursive (like navigating a tree/linked list), but in most languages, it shouldn't be relied on for most problems. Again, in most languages, you shouldn't try to recurse more than a few hundred times, or you'll risk blowing the stack and crashing your program. — Carcigenicate, Mar 14 '17 at 10:31
Also, look up how Python 3 implements its `range` function. Hint: in newer versions, it *doesn't* generate a full list of numbers for the range. — Carcigenicate, Mar 14 '17 at 10:50
@Carcigenicate "_Recursion...but in most languages, it shouldn't be relied on for most problems_" - this is wrong, unless you rephrase it to "...but in most imperative/OO languages" — , Mar 14 '17 at 14:22
Thanks, that gave me a lot to read and think about. Maybe there's a way to implement the same thing with a tail call which would be optimized. — Fuoco, Mar 14 '17 at 14:28
@ftor I was under the impression that the vast majority of "mainstream languages" are imperative focused. The only 2 functional languages I can think of that I know enjoy widespread use are Scala and maybe Clojure. But yes, imperative oriented languages *tend* to not support TCO, so you should be careful when using recursion. *Many* (but not necessarily all) functional orientated languages have some kind of support of TCO, or pseudo-TCO, like Scala's `@tail-call` annotation, or Clojure's `recur` special form (which isn't really TCO, but it's effectively the same). — Carcigenicate, Mar 14 '17 at 14:48
My point was that unless you know your recursive algorithm can and will be optimized, you should be careful when using recursion. — Carcigenicate, Mar 14 '17 at 14:49
@Carcigenicate Agreed. However, ES2015 has introduced TCO and eventually the engines will support it. So recursion becomes a serious alternative. Besides, I just looked into Haskell's optimization strategy - it is [amazing](http://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization) — , Mar 14 '17 at 15:20
@ftor That'll be nice. Javascript has been adopting more functional elements recently. It'll be sweet if it gets lazy lists for its `map` and `filter` functions. And haven't looked at Haskell's method. My head starts swimming as soon as the different strategies are explained. Clojure's method to emulating TCO has been described as amazing too, but my head exploded a bit when I read into it. — Carcigenicate, Mar 14 '17 at 15:24

score 1 · Answer 1 · answered Mar 13 '17 at 19:16

1

A more "canonical" form of the recursion (with out passing arrays and the reversing) would be:

function range(limit) {
  // end condition
  if (limit <= 0) return [];
  // main recursion
  var l = range(limit-1);
  l.push(limit);
  return l;
}

This is almost the same as yours, but it has a more "commonly" used structure.

answered Mar 13 '17 at 19:16

MaanooAk

2,418
17
28

Thanks! For some reason this is very obscure to me, I can't yet really understand how that works, let alone come up with such a solution. It does appear to run for a bit higher numbers than my original solution. – Fuoco Mar 14 '17 at 08:37
@Fuoco The difference between this and yours is the "base case" is checked and returbed immediately at the top. The base case is what allows the recursion to stop; it's your end condition. Typically, you'd expect to see the base case at the very top of the function. That's the most common place for it, and prevents any work from being done unnecessarily. I wouldn't expect it to allow for more recurses though. – Carcigenicate Mar 14 '17 at 10:37

score 1 · Answer 2 · 2017-03-14T09:44:48.957

Tail recursion and TCO

Recursion is the functional equivalence of imperative loops with an additional stack structure.

In getRange you don't use an additional stack structure but merely a plain for loop. This is the reason why you can express getRange with tail recursion, where the recursive call is the last expression inside the body of the recursive function. Tail recursion shares a single call stack frame for the entire recursive iteration, i.e. stack overflows are no longer possible.

Unfortunately, Javascript engines don't support tail recursion optimization (TCO) yet. Hence the stack overflow. But they will support TCO eventually.

Here is a more general approach, which follows the functional paradigm. sequence is a higher order function that takes a stepper function to create the sequence recursively. The result is accumulated in an array (acc). Now you can produce sequences of every data type that has an ordering:

const sequence = stepper => (x, y) => {
  const aux = (acc, z) => z <= y // inner auxiliary function
   ? aux(acc.concat(z), stepper(z)) // recursive case
   : acc; // base case

  return aux([], x);
};

const inc = x => x + 1;
const dbl = x => x * 2;
const succ = x => String.fromCharCode(x.charCodeAt(0) + 1);

console.log(sequence(inc) (1, 5)); // [1, 2, 3, 4, 5]
console.log(sequence(dbl) (2, 32)); // [2, 4, 8, 16, 32]
console.log(sequence(succ) ("c", "g")); // ["c", "d", "e", "f", "g"]

Generator functions

Generator functions are another means to create sequences. Please note that you don't need an accumulator anymore, because generator functions are stateful. To store the sequence you have to apply the function to a composite type that supports the Iterable protocol (like Array.from):

const sequence = stepper => (x, y) => {
  function* aux() {
    while (true) {
      yield x;
      x = stepper(x);
      if (x > y) break;
    }
  }

  return aux();
};

const sqr = x => x * x;

console.log(Array.from(sequence(sqr) (2, 256))); // [2, 4, 16, 256]

Wow, interesting! There really is still much to learn! I don't understand half of what's going on, but I have somewhere to strive now! — Fuoco, Mar 14 '17 at 14:31

A range function in Javascript written recursively

2 Answers2

Tail recursion and TCO

Generator functions