Primality test using recursion

For the given below exercise:


Here is one method to check if a number is prime:

def is_prime(n):
    k = 2
    while k < n:
        if n % k == 0:
            return False
        k += 1
    return True

How does this function work?


This is a decent way of testing if a number is prime, but looping k all the way to n
might be a bit cumbersome. As a little bonus question, can you think of a better place
to stop?


Using the is_prime function, fill in the following procedure, which generates the nth
prime number. For example, the 2nd prime number is 3, the 5th prime number is 11,
and so on.

def nth_prime(n):

Below is the solution:

def is_prime(n):
    def f(n, k):
        if k > (n // 2):
            return True
        elif n % k == 0:
            return False
        else:
            return f(n, k + 1)
    return f(n, 2)

def nth_prime(n):
    def traverse_for_nth_prime(count, k):
        if count == n:
           return k-1
        elif is_prime(k):
            return traverse_for_nth_prime(count + 1, k + 1)
        else:
            return traverse_for_nth_prime(count, k + 1)
    return traverse_for_nth_prime(0, 2)

print(nth_prime(20))

Above code is written in functional paradigm. Can it be improved, especially in relation to being optimised from recursion depth limit perspective, by strictly following functional paradigm?

A "functional" method avoiding recusion would be

from itertools import count

def gen_primes():
    return filter(is_prime, count(2))

def nth(n, iterable):
    return next(val for i, val in enumerate(iterable) if i == n)

def nth_prime(n):
    return nth(n, gen_primes())

To prove that this is functional, here's the Haskell:

enumerate = zip [0..]

primes = filter is_prime [2..]

nth iterable n = head [v | (i, v) <- enumerate iterable, i == n]

nth_prime = nth primes

The trick is to make everything as small as logically possible and see how to extract common functionality.

StackExchange Code Review Q#82819, answer score: 6