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