Maximum call stack size exceeded JS

Question

I'm trying to understand the concept of recursion and wanted to use it in my code (the getUniqueInt function):

var getRandomInt = function (min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
};

var getChosenNumbers = function (min, max) {
  var chosenNumbers = [];
  for (var k = min; k <= max; k++) {
    chosenNumbers.push(k);
  }
  return chosenNumbers;
};

var arrayOfNumbers = getChosenNumbers(1, 8);

var getUniqueInt = function (min, max) {
  var uniqueNumber;
  var randomNumber = getRandomInt(min, max);
  if (arrayOfNumbers.indexOf(randomNumber) !== -1) {
    uniqueNumber = randomNumber;
    arrayOfNumbers.splice(arrayOfNumbers.indexOf(uniqueNumber), 1);
  } else {
    uniqueNumber = getUniqueInt(min, max);
  }
  return uniqueNumber;
};

But I end up getting this: Uncaught RangeError: Maximum call stack size exceeded

What am I doing wrong? And does my code (I mean the recursion part) make any sense or it's totally wrong?

Mulan · Accepted Answer

But what I am basically trying to do here is to get a range of numbers (array of numbers) and then choose one of these numbers randomly without repeating the already chosen ones;

Your getRandomInt function is a good start -

const getRandomInt = (min = 0, max = 0) =>
  Math.floor(Math.random() * (max - min)) + min

Let's make a function to make a range of numbers -

const makeRange = (min = 0, max = 0) =>
  min > max
    ? []
    : [ min, ...makeRange(min + 1, max) ]

We don't have to loop to find the next random value. We can swap elements in an array to efficiently create a random sequence. This technique is known as Fisher-Yates shuffle -

const getUniqueRandom = (min = 0, max = 0) =>
{ const r = makeRange(min, max)

  const next = (i = 0) =>
  { if (i >= r.length) return undefined
    swap(r, i, getRandomInt(i, r.length))
    return r[i]
  }

  let i = 0
  const rand = () =>
    next(i++)

  return rand
}

Finally we need to write the swap function -

const swap = (a = [], i = 0, j = 0) =>
  [a[j], a[i]] = [a[i], a[j]]

Now here's how it works -

const rand = getUniqueRandom(3,7)

console.log(rand()) // 4
console.log(rand()) // 7

Keep calling it to get the rest of the values. It returns undefined when there is no possible unique to output -

console.log(rand()) // 3
console.log(rand()) // 6
console.log(rand()) // 5
console.log(rand()) // undefined

Expand the snippet below to verify the output in your own browser. Press Run many times to see the randomised outputs -

const getRandomInt = (min = 0, max = 0) =>
  Math.floor(Math.random() * (max - min)) + min

const makeRange = (min = 0, max = 0) =>
  min > max
    ? []
    : [ min, ...makeRange(min + 1, max) ]
    
const swap = (a = [], i = 0, j = 0) =>
  [a[j], a[i]] = [a[i], a[j]]

const getUniqueRandom = (min, max) =>
{ const r = makeRange(min, max)
  
  const next = (i = 0) =>
  { if (i >= r.length)
      return undefined
    swap(r, i, getRandomInt(i, r.length))
    return r[i]
  }
  
  let i = 0
  const rand = () =>
    next(i++)
  
  return rand
}
      
const rand = getUniqueRandom(3,7)

console.log(rand()) // 4
console.log(rand()) // 7
console.log(rand()) // 3
console.log(rand()) // 6
console.log(rand()) // 5
console.log(rand()) // undefined

generators

What rand demonstrates above is some sort of generator. Modern JavaScript has native support for Generators allowing us to write this program in a convenient way. You may have heard them called coroutines in other languages.

Here's a very simple generator we can use for makeRange. Note the use of yield instead of return -

const makeRange = function* (min = 0, max = 0)
{ while (min <= max)
    yield min++
}

And here's a rewrite of getUniqueRandom. We can gather all the values from makeRange(...) by using Array.from -

const getUniqueRandom = function* (min, max)
{ const r =
    Array.from(makeRange(min, max))

  for (let i = 0; i < r.length; i++)
  { swap(r, i, getRandomInt(i, r.length))
    yield r[i]
  }
}

To get the unique randoms out one-by-one -

const rand = getUniqueRandom(3,7)

console.log(rand.next()) // { value: 7, done: false }
console.log(rand.next()) // { value: 3, done: false }

Just as before, keep calling to get the next unique randoms. We see value: undefined and done: true when there are no more results -

console.log(rand.next()) // { value: 6, done: false }
console.log(rand.next()) // { value: 5, done: false }
console.log(rand.next()) // { value: 4, done: false }
console.log(rand.next()) // { value: undefined, done: true }

Just like we did with makeRange, if we want all of the results right away, we can simply use Array.from -

console.log(Array.from(getUniqueRandom(3, 7)))
// [ 6, 3, 4, 5, 7 ]

Expand the snippet below to verify the output in your own browser. Press Run many times to see the randomised outputs -

const getRandomInt = (min = 0, max = 0) =>
  Math.floor(Math.random() * (max - min)) + min

const swap = (a = [], i = 0, j = 0) =>
  [a[j], a[i]] = [a[i], a[j]]
      
const makeRange = function* (min = 0, max = 0)
{ while (min <= max)
    yield min++
}

const getUniqueRandom = function* (min, max)
{ const r =
    Array.from(makeRange(min, max))

  for (let i = 0; i < r.length; i++)
  { swap(r, i, getRandomInt(i, r.length))
    yield r[i]
  }
}

const rand = getUniqueRandom(3,7)

console.log(rand.next()) // { value: 7, done: false }
console.log(rand.next()) // { value: 3, done: false }
console.log(rand.next()) // { value: 6, done: false }
console.log(rand.next()) // { value: 5, done: false }
console.log(rand.next()) // { value: 4, done: false }
console.log(rand.next()) // { value: undefined, done: true }

console.log(Array.from(getUniqueRandom(3, 7)))
// [ 6, 3, 4, 5, 7 ]

Maximum call stack size exceeded JS

Answers (2)

Related Questions