Test prime number program

Question

I'm trying to write a program in JS that takes an input and tests whether or not it is a prime number using recursion.

In my code, I've created the function isPrime. As my 'base' I return false if x==1 and true if x==2 since 2 is the first prime number.

After that, I have an if statements that tests whether or not x is prime.
When I execute the code however, my console returns Uncaught RangeError: Maximum call stack size exceeded.
I'm not sure exactly why the program returns an error code.

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

Found a better solution:

const isPrime = (n, i = 2) => {
    
    // if it's 1 or 0 no primes
    if(n === 1 || n === 0) return false
    
    // check prime  and stop at the number
    if(n === i) return true
    
    // if it's divisible
    if(n % i == 0)  return false
    i++
    return isPrime(n,i)
}

Answer 2

Problems with current code

There are two real problems with your function. First, you have a bunch of unreachable code:

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.

}

Second, although you do properly include base cases, you never progress towards them:

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

For recursion to work, your recursive cases must somehow progress toward a base case. The progression may be complex, but if you can't demonstrate that each successive call is somehow closer to the base case, then you don't even know if your program can complete, let alone if it's correct.

Why choose recursion?

But I have a more fundamental question. Why do you want to use recursion here? Is it a learning exercise for you, either homework or your own personal studies? If so, that's fine. It's a perfectly legitimate problem to learn on.

But recursion and iteration are equally powerful. It's fairly easy to demonstrate that anything you can do with one, you can do with the other. So the choice usually comes down to whether your data structure is better suited for recursion or iteration. There are many structures for which recursion is clearly the best choice. If you're processing a tree structure, for instance, recursion will almost always be cleaner and more elegant. (Performance is a separate question, and will get into things like tail recursion.) If you're processing a complete list of items, either recursion or iteration might be better.

But here the problem is one of finding any divisors, stopping at the first one. You can do this with a simple iteration: is it divisible by 2?, is it divisible by 3?, is it divisible by 4?, ..., stopping on the first yes. Recursion adds nothing that makes this particularly cleaner.

(Note that one important performance improvement is to stop as soon as we pass the square root of our target value, since if there are factors, one of them has to be less than the square root.)

A recursive solution

That said, one certainly can use recursion to implement that. Here is how I might write it:

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

Or, in the style of your current code,

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

And, while we could also write that as

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

I think that make it harder to understand the recursion.

A better problem for recursion practice

Finally, if this is designed to help you learn recursion, let me suggest a related problem where recursion is more likely appropriate. Write a function to find all the prime factors of 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]

Again, this can be done iteratively or recursively, but I think the recursive solutions are likely to be nicer code.

Answer 3

To understand why, a good practice can be to log the arguments being passed to your function and limit the recursion. Try this with a small x like 10, and think about what's happening.

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

}

Answer 4

Here logic code for check number is prime or not

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

in your code

if (number == 1) {
    return false;
  } else if (number == 2) {
    return true;
  } else {
    return isPrime(number, ++divisor); // this is infinite recursion acurring 
  }