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: stackoverflow.com/questions/6095530/… — Tom O.
– Tom O., Commented Oct 20, 2017 at 14:02
I think it would be helpful to explain what you're trying to do. — C. Helling
– C. Helling, Commented Oct 20, 2017 at 14:06
What is the expected result of else { randomN = generateRandomNumber(array, maxN); }? — guest271314
– guest271314, Commented Oct 20, 2017 at 14:08
What is arr? Do you supply an array of numbers that you want to exclude? — MinusFour
– MinusFour, Commented Oct 20, 2017 at 14:26

Bergi · Accepted Answer · 2017-10-20 14:12:37Z

2

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.

answered Oct 20, 2017 at 14:12

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

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

2 Comments

Aessandro Over a year ago

" 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

Bergi Over a year ago

@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 for an example

llama · Accepted Answer · 2017-10-20 14:50:39Z

0

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];
    }
}

edited Oct 20, 2017 at 14:50

answered Oct 20, 2017 at 14:14

llama

2,53715 silver badges11 bronze badges

4 Comments

llama Over a year ago

@Alex: The array is cleared when the length becomes equal to maxN, so it'll be cleared when it's 5.

Aessandro Over a year ago

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

llama Over a year ago

@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 Over a year ago

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.

Collectives™ on Stack Overflow

JS maximum call stack exceeded

2 Answers 2

2 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related