Программа тестирования простых чисел - PullRequest
Новая
       8

Программа тестирования простых чисел

1 голос
/ 04 октября 2019

Я пытаюсь написать программу на 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);
  }

}

Ответы [ 3 ]

2 голосов
/ 04 октября 2019

Здесь логический код для номера чека прост или нет 

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


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


function isPrime(n)
{

  if (n===1)
  {
    return false;
  }
  else if(n === 2)
  {
    return true;
  }
  else
  {
    for(var x = 2; x < n; x++)
    {
      if(n % x === 0)
      {
        return false;
      }
    }
    return true;  
  }
}

в вашем коде 

if (number == 1) {
    return false;
  } else if (number == 2) {
    return true;
  } else {
    return isPrime(number, ++divisor); // this is infinite recursion acurring 
  }
0 голосов
/ 05 октября 2019

Проблемы с текущим кодом

Есть две настоящие проблемы с вашей функцией. Во-первых, у вас есть куча недоступного кода: 

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]

Опять же, это можно сделать итеративно или рекурсивно, но я думаю, что рекурсивные решения, вероятно, будут более приятным кодом.

0 голосов
/ 04 октября 2019

Чтобы понять почему, хорошей практикой может быть регистрация аргументов, передаваемых вашей функции, и ограничение рекурсии. Попробуйте это с маленьким x как 10, и подумайте о том, что происходит. 

var iterations = 20

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) {
  console.log(JSON.stringify(Array.from(arguments)));
  // stop infinite recursion
  if (iterations-- < 0)
    return;

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

}
...