1

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!

Improve this question
13
  • 1
    In the recursive solution, you should be prepending not appending. That reverse will be killer. Commented Mar 13, 2017 at 18:54
  • And the recursive solution will fail with a StackOverflow eventually. What does the iterative solution fail with? Commented Mar 13, 2017 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 Commented Mar 13, 2017 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. Commented Mar 13, 2017 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... Commented Mar 14, 2017 at 8:30

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

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 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.
1

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]

Improve this answer

2 Comments

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!
That's the spirit! Sorry that I could not help more.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.