Using generator expressions

We've shown some examples of generator expressions already. We'll show some more later in the chapter. We'll introduce some more generator techniques in this section.

It's common to see generator expressions used to create the list or dict literals through list comprehension or a dict comprehension syntax. This example, [x**2 for x in range(10)], is a list comprehension, sometimes called a list display.  For our purposes, the list display (or comprehension) is one of several ways to use generator expressions.  A collection display includes the enclosing literal syntax. In this example, the list literal [] characters wrap the generator: [x**2 for x in range(10)]. This is a list comprehension; it creates a list object from the enclosed generator expression, x**2 for x in range(10). In this section, we're going to focus on the generator expression separate from the list object.

A collection object and a generator expression have some similar behaviors because both are iterable. They're not equivalent, as we'll see in the following code. Using displays has the disadvantage of creating a (potentially large) collection of objects. A generator expression is lazy and creates objects only as required; this can improve performance.

We have to provide two important caveats on generator expressions, as follows:

• Generators appear to be sequence-like. The few exceptions include using a function such as the len() function that needs to know the size of the collection.
• Generators can be used only once. After that, they appear empty. 

Here is a generator function that we'll use for some examples:

def pfactorsl(x: int) -> Iterator[int]:
    if x % 2 == 0:
        yield 2
        if x//2 > 1:
            yield from pfactorsl(x//2)
        return
    for i in range(3, int(math.sqrt(x)+.5)+1, 2):
        if x % i == 0:
            yield i
            if x//i > 1:
                yield from pfactorsl(x//i)
            return
    yield x

We're locating the prime factors of a number. If the number, x, is even, we'll yield 2 and then recursively yield all prime factors of x/2.

For odd numbers, we'll step through odd values greater than or equal to 3 to locate a candidate factor of the number. When we locate a factor, i, we'll yield that factor, and then recursively yield all prime factors of x÷i.

In the event that we can't locate a factor, the number, x, must be prime, so we can yield the number.

We handle 2 as a special case to cut the number of iterations in half. All prime numbers, except 2, are odd.

We've used one important for loop in addition to recursion. This explicit loop allows us to easily handle numbers that have as many as 1,000 factors. (As an example, , a number with 300 digits, will have 1,000 factors.) Since the for variable, i, is not used outside the indented body of the loop, the stateful nature of the i variable won't lead to confusion if we make any changes to the body of the loop.

This example shows how to do tail-call optimization manually. The recursive calls that count from 3 to   have been replaced with a loop. The for loop saves us from a deeply recursive call stack.

Because the function is iterable, the yield from statement is used to consume iterable values from the recursive call and yield them to the caller.

As an alternative, the following definition is a more purely recursive version:

def pfactorsr(x: int) -> Iterator[int]:
    def factor_n(x: int, n: int) -> Iterator[int]:
        if n*n > x:
            yield x
            return
        if x % n == 0:
            yield n
            if x//n > 1:
                yield from factor_n(x//n, n)
        else:
            yield from factor_n(x, n+2)
    if x % 2 == 0:
        yield 2
        if x//2 > 1:
            yield from pfactorsr(x//2)
        return
    yield from factor_n(x, 3)  

We defined an internal recursive function, factor_n(), to test factors, n, in the range . If the candidate factor, n, is outside the range, then x is prime. Otherwise, we'll see whether n is a factor of x. If so, we'll yield n and all factors of . If n is not a factor, we'll evaluate the function recursively using . This uses recursion to test each value of . While this is simpler than the for statement version shown previously, it can't handle numbers with over 1,000 factors because of Python's stack limitation.

The outer function handles some edge cases. As with other prime-related processing, we handle two as a special case. For even numbers, we'll yield two and then evaluate pfactorsr() recursively for x÷2. All other prime factors must be odd numbers greater than or equal to 3. We'll evaluate the factors_n() function starting with 3 to test these other candidate prime factors.