**π‘ 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.