recursion Javascript to get prime numbers

Recursion in Javascript to Get Prime Numbers#

As a programmer, I have been fascinated by the concept of recursion in programming. Recursion is a technique where a function calls itself repeatedly until a base condition is met. It is an elegant way of solving problems that have repetitive substructures.

One such problem is finding prime numbers. A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In other words, it is a number that is divisible only by 1 and itself.

Implementation#

One way to implement recursion in Javascript to find prime numbers is as follows:

function isPrime(num, div) {
    if (num <= 2) {
        return (num === 2) ? true : false;
    }
    if (num % div === 0) {
        return false;
    }
    if (div * div > num) {
        return true;
    }
    return isPrime(num, div + 1);
}

function getPrimes(n) {
    var primes = [];
    for (var i = 2; i <= n; i++) {
        if (isPrime(i, 2)) {
            primes.push(i);
        }
    }
    return primes;
}

The isPrime function takes two arguments: the number to check whether it's prime and the divisor to check if it divides the number evenly. The function checks if the number is less than or equal to 2. If it is, it returns true if the number is 2 and false otherwise. If the number is greater than 2, it checks if the divisor divides the number evenly. If it does, it returns false. If the product of the divisor and itself is greater than the number, it returns true. If none of these conditions are met, it calls itself with an incremented divisor.

The getPrimes function takes a number n and returns an array of prime numbers from 2 to n. It initializes an empty array called primes and iterates over numbers from 2 to n. For each number, it calls the isPrime function with a divisor of 2. If the isPrime function returns true, it adds the number to the primes array.

Example Usage#

Here's an example of how to use the getPrimes function:

var primes = getPrimes(20);
console.log(primes); // [2, 3, 5, 7, 11, 13, 17, 19]

In this example, we call the getPrimes function with a parameter of 20. The function returns an array of prime numbers from 2 to 20, which we then log to the console.

Alternative Implementation#

Another way to implement recursion in Javascript to find prime numbers is as follows:

function isPrime(num, div) {
    if (num === div) {
        return true;
    }
    if (num % div === 0) {
        return false;
    }
    return isPrime(num, div + 1);
}

function getPrimes(n, i) {
    if (i === 1) {
        return [];
    }
    var primes = getPrimes(n, i - 1);
    if (isPrime(i, 2)) {
        primes.push(i);
    }
    return primes;
}

The isPrime function is the same as in the previous implementation. The getPrimes function takes two arguments: the upper limit of the range to check and the current number being checked. If the current number is 1, it returns an empty array. Otherwise, it calls itself with the same upper limit and the previous number. It then checks if the current number is prime by calling the isPrime function with a divisor of 2. If it is prime, it adds the number to the array of primes returned by the recursive call.

Example Usage#

Here's an example of how to use the alternative getPrimes function:

var primes = getPrimes(20, 20);
console.log(primes); // [2, 3, 5, 7, 11, 13, 17, 19]

In this example, we call the getPrimes function with parameters of 20 and 20. The function returns an array of prime numbers from 2 to 20, which we then log to the console.