Functional programs don't rely on loops and the associated overhead of tracking the state of loops. Instead, functional programs try to rely on the much simpler approach of recursive functions. In some languages, the programs are written as recursions, but Tail-CallOptimization (TCO) in the compiler changes them to loops. We'll introduce some recursion here and examine it closely in Chapter 6, Recursions and Reductions.

We'll look at a simple iteration to test a number for being prime. A prime number is a natural number, evenly divisible by only 1 and itself. We can create a naïve and poorly-performing algorithm to determine whether a number has any factors between 2 and the number. This algorithm has the advantage of simplicity; it works acceptably for solving Project Euler problems. Read up on Miller-Rabin primality tests for a much better algorithm.

We'll use the term coprime to mean that two numbers have only one as their common factor. The numbers 2 and 3, for example, are coprime. The numbers 6 and 9, however, are not coprime because they have three as a common factor.

If we want to know whether a number, n, is prime, we actually ask this: is the number n coprime to all prime numbers, p, such that p² < n? We can simplify this using all integers, p, so that 2 ≤ p² < n.

Sometimes, it helps to formalize this as follows:

The expression could look as follows in Python:

not any(n%p==0 for p in range(2,int(math.sqrt(n))+1))

A more direct conversion from mathematical formalism to Python would use all(n%p != 0... ), but that requires strict evaluation of all values of p. The not any version can terminate early if a True value is found.

This simple expression has a for loop inside it: it's not a pure example of stateless functional programming. We can reframe this into a function that works with a collection of values. We can ask whether the number, n, is coprime within any value in the half-open interval . This uses the symbols [) to show a half-open interval: the lower values are included, and the upper value is not included. This is typical behavior of the Python range() function. We will also restrict ourselves to the domain of natural numbers. The square root values, for example, are implicitly truncated to integers.

We can think of the definition of prime as the following: 

, given n > 1.

When defining a recursive function over a simple range of values, the base case can be an empty range. A non-empty range is handled recursively by processing one value combined with a range that's narrower by one value. We could formalize it as follows:

This version is relatively easy to confirm by examining the two cases, which are given as follows:

• If the range is empty, , we evaluated something like: . The range contains no values, so the return is a trivial True.
• If the range is not empty, we evaluated something like: . This decomposes into . For this example, we can see that the first clause is True, and we'll evaluate the second clause recursively.

As an exercise for the reader, this recursion can be redefined to count down instead of up, using [a,b-1) in the second case. Try this revision to see what, if any, changes are required.

As a side note, some folks like to think of the empty interval as a ≥ b instead of the a = b. The extra condition is needless, since a is incremented by one and we can easily guarantee that a ≤ b, initially. There's no way for a to somehow leap past b through some error in the function; we don't need to over-specify the rules for an empty interval.

Here is a Python code snippet that implements this definition of prime:

def isprimer(n: int) -> bool:
    def isprime(k: int, coprime: int) -> bool:
        """Is k relatively prime to the value coprime?""" 
        if k < coprime*coprime: return True 
        if k % coprime == 0: return False 
        return isprime(k, coprime+2) 
    if n < 2: return False 
    if n == 2: return True 
    if n % 2 == 0: return False 
    return isprime(n, 3)

This shows a recursive definition of an isprimer() function. The function expects an int value for the n parameter. The type hints suggest it will return a bool result.

The half-open interval, , is reduced to just the low-end argument, a, which is renamed to the coprime parameter to clarify its purpose. The base case is implemented as n < coprime*coprime; the range of values from coprime to 1+math.sqrt(n) would be empty.

Rather than use a non-strict and operation, this example splits the decision into a separate if statement, if n % coprime == 0. The final return statement is the recursive call with a different coprime test value.

Because the recursion is the tail end of the function, this is an example of Tail recursion.

This isprime() function is embedded in the isprimer() function. The outer function serves to establish the boundary condition that n is an odd number greater than 2. There's no point in testing even numbers for being prime, since 2 is the only even prime.

What's important in this example is that the two cases of this recursive function are quite simple to design. Making the range of values an explicit argument to the internal isprime() function allows us to call the function recursively with argument values that reflect a steadily shrinking interval.

While recursion is often succinct and expressive, we have to be cautious about using it in Python. There are two problems that can arise:

• Python imposes a recursion limit to detect recursive functions with improperly defined base cases
• Python does not have a compiler that does TCO

The default recursion limit is 1,000, which is adequate for many algorithms. It's possible to change this with the sys.setrecursionlimit() function. It's not wise to raise this arbitrarily since it might lead to exceeding the OS memory limitations and crashing the Python interpreter.

If we try a recursive isprimer() function on a value of n over 1,000,000, we'll run afoul of the recursion limit. Even if we modified the isprimer() function to only check prime factors instead of all factors, we'd be stopped at the 1,000th prime number, 7,919, limiting our prime testing to numbers below 62,710,561.

Some functional programming languages can optimize simple recursive functions. An optimizing compiler will transform the recursive evaluation of the isprimer(n, coprime+1) method into a low-overhead loop. The optimization tends to make debugging optimized programs more difficult. Python doesn't perform this optimization. Performance and memory are sacrificed for clarity and simplicity. This also means we are forced to do the optimization manually.

In Python, when we use a generator expression instead of a recursive function, we essentially do the TCO manually. We don't rely on a compiler to do this optimization.

Here is TCO done as a generator expression:

def isprimei(n: int) -> bool:
    """Is n prime?

    >>> isprimei(2)
    True
    >>> tuple( isprimei(x) for x in range(3,11) )
    (True, False, True, False, True, False, False, False)
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, 1+int(math.sqrt(n)), 2):
        if n % i == 0:
            return False
    return True

This function includes many of the functional programming principles, but it uses a generator expression instead of a pure recursion.

This algorithm is slow for large primes. For composite numbers, the function often returns a value quickly. If used on a value such as , it will take a few minutes to show that this is prime. Clearly, the slowness comes from checking 1,518,500,249 individual candidate factors.