javascript - 测试素数程序

Question

我正在尝试用 JS 编写一个程序，该程序接受输入并使用递归测试它是否是素数。

在我的代码中，我创建了函数 isPrime。作为我的“基础”，我返回 false 如果 x==1 和 true 如果 x==2 因为 2 是第一个素数。

之后，我有一个 if 语句来测试 x 是否为质数。
但是，当我执行代码时，我的控制台返回 Uncaught RangeError: Maximum call stack size exceeded。
我不确定程序返回错误代码的确切原因。

let x = prompt("Enter a number to test as a prime number: ");
let result = isPrime(x, 2);

if (result) {
  alert("x is prime");
} else {
  alert("x is not prime");
}

function isPrime(number, divisor) {
  if (number == 1) {
    return false;
  } else if (number == 2) {
    return true;
  } else {
    return isPrime(number, ++divisor);
  }

  if (number % divisor == 0) {
    return false;
  } else if (divisor ** 2 >= number) {
    return true;
  } else {
    return isPrime(number, ++divisor);
  }

}

Answer 1

当前代码的问题

您的功能有两个真正的问题。首先，你有一堆无法访问的代码:

function isPrime(...) {
  if (...) {
    return false
  } else if (...) {
    return true
  } else {
    return isPrime(...)
  }

  // Everything from here down cannot be reached.  You already returned from this
  // function in one branch or another in the block above.

}

其次，尽管您确实正确地包含了基本案例，但您永远不会朝着它们前进:

function isPrime(number, divisor) {
  if (number == 1) {                    // Base case, testing on `number`
    return false;
  } else if (number == 2) {             // Base case, testing on `number`
    return true;
  } else {
    return isPrime(number, ++divisor);  // Recursive case, doesn't change `number`
  }

  // Even if you could reach this section, it has the same problem.
}

要使递归起作用，您的递归案例必须以某种方式朝着基本案例发展。进程可能很复杂，但如果您不能证明每个连续的调用都以某种方式更接近基本情况，那么您甚至不知道您的程序是否可以完成，更不用说它是否正确了。

为什么选择递归？

但我有一个更基本的问题。为什么要在这里使用递归？这对你来说是一种学习练习，家庭作业还是你自己的个人学习？如果是这样，那很好。这是一个值得学习的完全合理的问题。

但是递归和迭代同样强大。很容易证明你可以用一个做任何事情，你也可以用另一个做。因此，选择通常取决于您的数据结构是否更适合递归或迭代。递归显然是许多结构的最佳选择。例如，如果你正在处理一个树结构，递归几乎总是更干净、更优雅。 (性能是一个单独的问题，并且会涉及尾递归等问题。)如果您正在处理一个完整的项目列表，递归或迭代可能更好。

但这里的问题是找到任何除数，停在第一个。您可以通过简单的迭代来做到这一点:它能被 2 整除吗？，它能被 3 整除吗？，它能被 4 整除吗？ , ..., 停在第一个是。递归没有添加任何使它特别清晰的内容。

(请注意，一个重要的性能改进是在我们超过目标值的平方根时立即停止，因为如果有因素，其中一个必须小于平方根。)

递归解决方案

也就是说，当然可以使用递归来实现它。我可能会这样写:

const isPrime = (n, d = 2) =>
  d * d > n
    ? true
  : n % d == 0
    ? false
  : isPrime (n, d + 1)

console .log (isPrime (40)) //=> false
console .log (isPrime (41)) //=> true

或者，按照您当前代码的风格，

function isPrime(n, d = 2) {
  if (d * d > n) {
    return true;
  } else  if (n % d == 0) {
    return false;
  } else {
    return isPrime(n , d + 1)
  }
}

而且，虽然我们可以也把它写成

const isPrime = (n, d = 2) =>
  d * d > n || (n % d !== 0 && isPrime (n, d + 1))

我认为这让理解递归变得更加困难。

一个更好的递归练习题

最后，如果这是为了帮助你学习递归，让我提出一个相关的问题，其中递归更合适。编写一个函数来求出 n 的所有质因数:

primeFactors(17)    //=> [17]
primeFactors(18)    //=> [2, 3, 3]
primeFactors(19)    //=> [19]
primeFactors(20)    //=> [2, 2, 5]

primeFactors(55440) //=> [2, 2, 2, 2, 3, 3, 5, 7, 11]

同样，这可以迭代或递归地完成，但我认为递归解决方案可能是更好的代码。