开发者问题收集

超出最大调用堆栈大小 JS

2019-09-03
1849

我试图理解递归的概念,并希望在我的代码(getUniqueInt 函数)中使用它:

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

但我最终得到了这个: Uncaught RangeError:超出最大调用堆栈大小

我做错了什么?我的代码(我的意思是递归部分)有意义吗?还是完全错误?

2个回答

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;

您的 getRandomInt 函数是一个很好的开始 -

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) ]

我们不必循环查找下一个随机值。我们可以 交换 数组中的元素以有效地创建随机序列。这种技术被称为 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
}

最后,我们需要编写 swap 函数 -

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

现在,它是这样工作的 -

const rand = getUniqueRandom(3,7)

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

继续调用它以获取其余值。当没有可能的唯一输出时,它返回 undefined -

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

展开下面的代码片段以在您自己的浏览器中验证输出。多次按下 Run 按钮可查看随机输出 -

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

生成器

上面 rand 演示的是某种 生成器 。现代 JavaScript 原生支持 生成器 ,这让我们能够以便捷的方式编写此程序。您可能在其他语言中听说过它们被称为 协同程序

这是一个非常简单的生成器,我们可以将其用于 makeRange 。请注意使用 yield 而不是 return -

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

以下是 getUniqueRandom 的重写。我们可以使用 Array.frommakeRange(...) 收集所有值 -

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 }

与之前一样,继续调用以获取下一个唯一随机数。当没有更多结果时,我们会看到 value: undefineddone: true -

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 }

就像我们对 makeRange 所做的那样,如果我们想立即获得所有结果,我们可以简单地使用 Array.from -

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

展开下面的代码片段以在您自己的浏览器中验证输出。多次按 Run 以查看随机输出 -

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 ]
Mulan
2019-09-03

您的代码没有意义,抱歉,原因如下

  • 设置 min=0,max=10

  • getRandomInt 返回 0-10 内的随机整数

  • getChosenNumbers 返回 0-10 之间的整数数组,即 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

  • arrayOfNumbers 现在是 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

getUniqueInt 根本无法获取 uniq,因为 getRandomInt 已在 getChosenNumbers

这就是为什么

 else {
    uniqueNumber = getUniqueInt(min, max);
  }

被调用无数次,因为

arrayOfNumbers.indexOf(randomNumber) !== -1

永远不会成立

Medet Tleukabiluly
2019-09-03