Recursive Techniques to Determine Prime Numbers in Python

π‘ 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.