Primality test using recursion
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) &lt;- 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.