JS maximum call stack exceeded

Question

I have this:

var Utilities = (function (array, maxN) {

  function generateRandomNumber(array, maxN) {
        let randomN = Math.floor(Math.random() * maxN) + 0;

        if(!array.includes(randomN)) {
            console.log(maxN);
            if(array.length == maxN) {
                console.log('max reached');
                array.length = 0;
                return;
            }
            else {
                array.push(randomN);
            }

        }
        else {
            randomN = generateRandomNumber(array, maxN);
        }
        return randomN;
    }

    return {
        generateRandomNumber: generateRandomNumber
    };

})();

export default Utilities;

and it's used like this on click:

function getRandomNumber(arr) {
    let randomN = Utilities.generateRandomNumber(arr, 5);
    return randomN;
}

however, when the length of 5 is reached I get: (although I am clearing the array) I am trying to generate a random number however I don't want to repeat it, so I store it inside a an array to check if it has been generated already. However the issue I have is that (even though I am clearing the array once the length is = to max number) I get the "error" attached

Slightly different question but may provide some insight: https://stackoverflow.com/questions/6095530/maximum-call-stack-size-exceeded-error — Tom O., Oct 20 '17 at 14:02
I think it would be helpful to explain what you're trying to do. — C. Helling, Oct 20 '17 at 14:06
What is the expected result of `else { randomN = generateRandomNumber(array, maxN); }`? — guest271314, Oct 20 '17 at 14:08
What is `arr`? Do you supply an array of numbers that you want to exclude? — MinusFour, Oct 20 '17 at 14:26

score 2 · Answer 1 · answered Oct 20 '17 at 14:12

however, when the length of 5 is reached I get a stack overflow, although I am clearing the array

No, you're not clearing the array - that would happen only when you found a new random number (that is not included in the array), which of course never happens when the array is full. You will need to do the length check at the beginning:

function generateRandomNumber(array, maxN) {
    if (array.length == maxN) {
        console.log('max reached');
        array.length = 0;
        return;
    }
    let randomN = Math.floor(Math.random() * maxN) + 0;
    if (!array.includes(randomN)) {
        array.push(randomN);
        console.log(maxN);
        return randomN;
    } else {
        return generateRandomNumber(array, maxN);
    }
}

Of course, this way of generating new random numbers by try-and-error is inefficient in general, and will take too many steps once maxN is very large and the array is nearly full. If the iteration is implemented as recursion, you will eventually get a stack overflow.

" this way of generating new random numbers by try-and-error is inefficient in general" would you suggest a better way? I happy to learn more. Thank you — Aessandro, Oct 20 '17 at 14:35
@Alex Keeping a list with the numbers that *are* still allowed to be produced, and selecting one of them randomly, requires no retries and can guarantee to always produce the next number in constant time. See [this implementation](https://stackoverflow.com/a/11809348/1048572) for an example — Bergi, Oct 20 '17 at 14:44

llama · Accepted Answer · 2017-10-20T14:50:39.330

It's because you should be pushing the item into the array as soon as you see that it's not in array, so that the item that brings the array to its max length is the one that also clears the array.

The way it is right now, the .push() that brings the array to its max doesn't clear the array, so on the next call, whatever number is produced will always be included in the array, making your recursion always happen.

function generateRandomNumber(array, maxN) {
    let randomN = Math.floor(Math.random() * maxN);

    if(!array.includes(randomN)) {
        if(array.push(randomN) == maxN) {
            console.log('max reached');
            array.length = 0;
        }
        return randomN;
    } else {
        return generateRandomNumber(array, maxN);
    }
}

I also made a proper tail call by returning immediately on the recursive call without it depending on any variable in the current scope. I also took advantage of the fact that .push() returns the new .length, so its return value can be used for the comparison.

I'd probably also rearrange it to use a positive condition.

function generateRandomNumber(array, maxN) {
    let randomN = Math.floor(Math.random() * maxN);

    if(array.includes(randomN)) {
        return generateRandomNumber(array, maxN);
    }

    if(array.push(randomN) == maxN) {
        console.log('max reached');
        array.length = 0;
    }
    return randomN;
}

And personally, I think the function should use its own array. I'd get rid of the array parameter, and put var array = []; inside the outmost IIFE function.

Since this needs to be reused, you could make a factory function that produces a unique function with its own array and max length.

function makeNumberGenerator(maxN) {
    var array = [];

    return function generateRandomNumber() {
        let randomN = Math.floor(Math.random() * maxN);

        if(array.includes(randomN)) {
            return generateRandomNumber(array, maxN);
        }

        if(array.push(randomN) == maxN) {
            console.log('max reached');
            array.length = 0;
        }
        return randomN;
    }
}

Then to use one of these, you'd first create a number generator for the desired size:

var randomGen5 = makeNumberGenerator(5);

Then use it without params, since it already has the max and the array.

var num = randomGen5(); // 2 (or whatever)

Here's a more efficient algorithm for producing a random number from a range:

function makeNumberGenerator(maxN) {
    // Add some code to ensure `maxN` is a positive integer

    var array = [];

    return function generateRandomNumber() {
        if(!array.length) {
          array = Array.from(Array(maxN), (_, i) => i);
        }
        return array.splice(Math.floor(Math.random() * array.length), 1)[0];
    }
}

@Alex: The array is cleared when the length becomes equal to `maxN`, so it'll be cleared when it's `5`. — llama, Oct 20 '17 at 14:33
That is a utility function which is being used in 2 more methods that need the same logic but different values in terms of maxN — Aessandro, Oct 20 '17 at 14:36
@Alex: Ah, of course. I'd still make that association by having a factory function produce a pairing of the number generator function with an array and its max length. This helps prevent passing some array that shouldn't be used for this purpose. — llama, Oct 20 '17 at 14:38
And Bergi is right about this not being a great way. It can cause much recursion even when the algorithm is correct. Instead you could start with a full array of numbers, and on each call, remove one from the array that's from `0` to its `.length-1`. By removing the item, the array shrinks on each call, and eventually becomes `0`, at which point, you replenish the array. — llama, Oct 20 '17 at 14:46

JS maximum call stack exceeded

2 Answers2