**π‘ Problem Formulation:** We often encounter situations in mathematics and programming where we need to determine whether a given number is prime or not. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, inputting the number 7 should return that it is a prime number, whereas inputting 8 should return that it is not prime.

## Method 1: Standard Recursion

This method employs classic recursion to check for a prime number. The function recursively divides the number by decrementing divisors and checks for remainders. If a number only divides evenly by itself and 1, it’s prime.

Here’s an example:

def is_prime(n, i=2): if n n: return True return is_prime(n, i + 1) print(is_prime(7)) print(is_prime(8))

Output:

True False

This snippet of code defines a recursive function `is_prime()`

that takes the number to be checked as `n`

and an initial divisor `i`

. The base cases handle numbers less than or equal to 2. The recursion occurs by incrementing `i`

and checking divisibility until `i`

squared is greater than `n`

.

## Method 2: Optimized Recursion With Halting

This variation improves efficiency by halting early if a divisor is found and only iterating up to the square root of the number.

Here’s an example:

def is_prime(n, divisor=None): if divisor is None: divisor = n - 1 while divisor >= 2: if n % divisor == 0: return False else: return is_prime(n, divisor-1) return True print(is_prime(29)) print(is_prime(30))

Output:

True False

In this code, the `is_prime()`

function introduces a `divisor`

parameter which decrements with each recursive call. If any divisor evenly divides `n`

, `False`

is returned, indicating the number is not prime. The recursion optimally ceases past the square root of `n`

.

## Method 3: Memoization to Speed Up Recursion

A memoization technique stores intermediate results to avoid repeated calculations during recursion, speeding up the checking on larger numbers.

Here’s an example:

def is_prime_memo(n, i=2, memo={}): if n in memo: return memo[n] if n n: memo[n] = True return True return is_prime_memo(n, i + 1, memo) print(is_prime_memo(7)) print(is_prime_memo(8))

Output:

True False

The function `is_prime_memo()`

uses a dictionary `memo`

to store the primality of numbers it has already calculated. This prevents recalculating for those numbers, allowing for more efficient recursive calls.

## Method 4: Recursion with Functional Programming

This approach uses functional programming principles, leveraging the filter function and lambda expressions in the recursion process to determine primality.

Here’s an example:

def is_prime_func(n, divisor=None): if divisor is None: divisor = n - 1 if divisor == 1: return True return False if n % divisor == 0 else is_prime_func(n, divisor - 1) print(is_prime_func(11)) print(is_prime_func(12))

Output:

True False

The `is_prime_func()`

function uses tail recursion in combination with conditional expressions. By avoiding any additional function calls or iterations when a divisor is found, it streamlines the recursive checking process.

## Bonus One-Liner Method 5: Lambda Recursion

This one-liner uses a lambda function within itself to provide a compact and elegant recursive solution to check for prime numbers.

Here’s an example:

is_prime_one_liner = (lambda f: lambda n: f(f, n, 2))(lambda self, n, i: False if n n else self(self, n, i+1)) print(is_prime_one_liner(13)) print(is_prime_one_liner(14))

Output:

True False

The one-liner leverages a Y-combinator-like pattern where a lambda function calls itself through an argument. This allows for recursion without the need for a named function, providing an exceedingly concise way to determine if a number is prime.

## Summary/Discussion

**Method 1:**Standard Recursion. Straightforward. May become inefficient for large numbers.**Method 2:**Optimized Recursion With Halting. Improved efficiency with early stopping. Still relatively simple to understand.**Method 3:**Memoization to Speed Up Recursion. Great for larger numbers due to caching. Slightly more complex due to memoization.**Method 4:**Recursion with Functional Programming. Concise. Recursive calls are optimized but may be less intuitive for beginners.**Bonus Method 5:**Lambda Recursion. Elegantly short and functional. Readability can be challenging, and debugging is difficult.

Emily Rosemary Collins is a tech enthusiast with a strong background in computer science, always staying up-to-date with the latest trends and innovations. Apart from her love for technology, Emily enjoys exploring the great outdoors, participating in local community events, and dedicating her free time to painting and photography. Her interests and passion for personal growth make her an engaging conversationalist and a reliable source of knowledge in the ever-evolving world of technology.