Generator

City University of Hong Kong

CS1302 Introduction to Computer Programming

%reload_ext divewidgets

Recursion

Consider computing the Fibonacci number of order nn:

Fn:={Fn−1+Fn−2n>1(recurrence)1n=1(base case)0n=0(base case).F_n := \begin{cases} F_{n-1}+F_{n-2} & n>1 \kern1em \text{(recurrence)}\\ 1 & n=1 \kern1em \text{(base case)}\\ 0 & n=0 \kern1em \text{(base case)}. \end{cases}
(1)

Fibonacci numbers have practical applications in generating pseudorandom numbers.

Can we define the function by calling the function itself?

Try stepping through such a function below to see how it works:

%%optlite -r -h 450
def fibonacci(n):
    if n > 1:
        return fibonacci(n - 1) + fibonacci(n - 2)  # recursion
    elif n == 1:
        return 1
    else:
        return 0


print(fibonacci(2))
%%optlite -r -h 550
def gcd(a, b):
    ### BEGIN SOLUTION
    return gcd(b, a % b) if b else a
    ### END SOLUTION


print(gcd(3 * 5, 5 * 7)) # gcd = ?

Is recursion strictly necessary?

E.g., the following computes the Fibonacci number using a while loop instead.

%%optlite -r -h 550
def fibonacci_iteration(n):
    if n > 1:
        _, F = 0, 1  # next two Fibonacci numbers
        while n > 1:
            _, F, n = F, F + _, n - 1
        return F
    elif n == 1:
        return 1
    else:
        return 0


fibonacci_iteration(3)
# more tests
for n in range(5):
    assert fibonacci(n) == fibonacci_iteration(n)
Solution to Exercise 2

The step-by-step execution of the recursion is how python implements a recursion as an iteration.

%%optlite -r -h 550
def gcd_iteration(a, b):
    ### BEGIN SOLUTION
    while b:
        a, b = b, a % b
    return a
    ### END SOLUTION


gcd_iteration(3 * 5, 5 * 7)
# test
for n in range(5):
    assert fibonacci(n) == fibonacci_iteration(n)

What are the benefits of recursion?

Is recusion more efficient than iteration?

%%timeit -n 1
# Assign n the appropriate value
### BEGIN SOLUTION
n = 34
### END SOLUTION
fibonacci(n)
%%timeit -n 1
# Assign n
### BEGIN SOLUTION
n = 400000
### END SOLUTION
fibonacci_iteration(n)

To understand the difference in performance, modify fibonacci to print each function call as follows.

def fibonacci_verbose(n):
    """Returns the Fibonacci number of order n."""
    print(f"fibonacci({n})")
    return fibonacci_verbose(n - 1) + fibonacci_verbose(n - 2) if n > 1 else 1 if n == 1 else 0


fibonacci_verbose(5)

There are many redundant computations. E.g., fibonacci(3) is called twice because

  • fibonacci(5) calls fibonacci(4) and fibonacci(3).
  • fibonacci(4) then calls fibonacci(3) and fibonacci(2).

Global Variables and Closures

Consider generating a sequence of Fibonacci numbers:

for n in range(5):
    print(fibonacci_iteration(n))
Solution to Exercise 5

No. Each call to fibonacci_iteration(n) recomputes the last two Fibonacci numbers Fn−1F_{n-1} and Fn−2F_{n-2} for n≥2n\geq 2.

How to avoid redundant computations?

One way is to store the last two computed Fibonacci numbers.

%%optlite -r -h 650
Fn, Fnn, n = 0, 1, 0  # global variables


def print_fibonacci_state():
    print(
        f"""Global states:
    Fn  : Next Fibonacci number      = {Fn}
    Fnn : Next next Fibonacci number = {Fnn}
    n   : Next order                 = {n}"""
    )


def next_fibonacci():
    """Returns the next Fibonacci number."""
    global Fn, Fnn, n  # global declaration
    value, Fn, Fnn, n = Fn, Fnn, Fn + Fnn, n + 1
    return value


for i in range(5):
    print(next_fibonacci())
print_fibonacci_state()

Why global is NOT needed in print_fibonacci_state?

Without ambiguity, Fn, Fnn, n in print_fibonacci_state are not local variables by Rule 1 because they are not defined within the function.

Why global is needed in next_fibonacci?

What would happen if the global statement is removed:

%%optlite -h 400
def next_fibonacci():
    """Returns the next Fibonacci number."""
    # global Fn, Fnn, n
    value = n
    n, Fnn, n = Fnn, n + Fnn, n + 1
    return value


next_fibonacci()

UnboundLocalError is raised (as supposed to NameError) because

  • the assignment in Line 5 defines n as a local variable by Rule 2, but
  • the assignment in Line 4 references n, which is not yet defined at that point.

Are global variables preferred over local ones?

Consider rewriting the for loop as a while loop:

%%optlite -h 650
Fn, Fnn, n = 0, 1, 0  # global variables


def print_fibonacci_state():
    print(
        f"""Global states:
    Fn  : Next Fibonacci number      = {Fn}
    Fnn : Next next Fibonacci number = {Fnn}
    n   : Next order                 = {n}"""
    )


def next_fibonacci():
    """Returns the next Fibonacci number."""
    global Fn, Fnn, n  # global declaration
    value, Fn, Fnn, n = Fn, Fnn, Fn + Fnn, n + 1
    return value


n = 0
while n < 5:
    print(next_fibonacci())
    n += 1
print_fibonacci_state()
Solution to Exercise 6

There is a name collision. n is also incremented by next_fibonacci(), and so the while loop is only executed 3 times in total.

To avoid such error, a convention in python is to use a leading underscore for variable names that are private (for internal use):

_single_leading_underscore: weak "internal use" indicator. E.g., from M import * does not import objects whose names start with an underscore.

%%optlite -h 600
_Fn, _Fnn, _n = 0, 1, 0  # global variables


def print_fibonacci_state():
    print(
        f"""Global states:
    _Fn  : Next Fibonacci number      = {_Fn}
    _Fnn : Next next Fibonacci number = {_Fnn}
    _n   : Next order                 = {_n}"""
    )


def next_fibonacci():
    """Returns the next Fibonacci number."""
    global _Fn, _Fnn, _n  # global declaration
    value, _Fn, _Fnn, _n = _Fn, _Fnn, _Fn + _Fnn, _n + 1
    return value


n = 0
while n < 5:
    print(next_fibonacci())
    n += 1
print_fibonacci_state()

Is it possible to store the function states without using global variables?

We can use nested functions and nonlocal variables.

def fibonacci_sequence(Fn, Fnn):
    def next_fibonacci():
        """Returns the next (generalized) Fibonacci number starting with
        Fn and Fnn as the first two numbers."""
        nonlocal Fn, Fnn, n  # declare nonlocal variables
        value = Fn
        Fn, Fnn, n = Fnn, Fn + Fnn, n + 1
        return value

    def print_fibonacci_state():
        print(
            """States:
        Next Fibonacci number      = {}
        Next next Fibonacci number = {}
        Next order                 = {}""".format(
                Fn, Fnn, n
            )
        )

    n = 0  # Fn and Fnn specified in the function arguments
    return next_fibonacci, print_fibonacci_state


next_fibonacci, print_fibonacci_state = fibonacci_sequence(0, 1)
n = 0
while n < 5:
    print(next_fibonacci())
    n += 1
print_fibonacci_state()

The state variables Fn, Fnn, n are now encapsulated, and the functions returned by fibonacci_sequence no longer depend on any global variables.

Another benefit of using nested functions is creating different Fibonacci sequences with different base cases.

my_next_fibonacci, my_print_fibonacci_state = fibonacci_sequence("cs", "1302")
for n in range(5):
    print(my_next_fibonacci())
my_print_fibonacci_state()

next_fibonacci and print_fibonacci_state are local functions of fibonacci_sequence.

Each local function has an attribute named __closure__ that stores the captured local variables.

def print_closure(f):
    """Print the closure of a function."""
    print("closure of ", f.__name__)
    for cell in f.__closure__:
        print("    {} content: {!r}".format(cell, cell.cell_contents))


print_closure(next_fibonacci)
print_closure(print_fibonacci_state)

Generator

An easier way to generate a sequence of objects one by one is to write a generator.

fibonacci_generator = (fibonacci_iteration(n) for n in range(3))
fibonacci_generator

The above uses a generator expression to define fibonacci_generator.

How to obtain items from a generator?

We can use the next function.

fibonacci_generator = (fibonacci_iteration(n) for n in range(3))

while True:
    print(next(fibonacci_generator))  # raises StopIterationException eventually

A generator object is iterable, i.e., it implements both __iter__ and __next__ methods that are automatically called in a for loop as well as the next function.

fibonacci_generator = (fibonacci_iteration(n) for n in range(5))

for fib in fibonacci_generator:  # StopIterationException handled by for loop
    print(fib)

Is fibonacci_generator efficient?

No, again, due to redundant computations. A better way to define the generator is to use the keyword yield:

%%optlite -h 450
def fibonacci_sequence(Fn, Fnn, stop):
    """Return a generator that generates Fibonacci numbers
    starting from Fn and Fnn until stop (exclusive)."""
    while Fn < stop:
        yield Fn  # return Fn and pause execution
        Fn, Fnn = Fnn, Fnn + Fn


for fib in fibonacci_sequence(0, 1, 5):
    print(fib)
def fibonacci_sequence(Fn, Fnn, stop):
    ### BEGIN SOLUTION
    """Return a generator that generates Fibonacci numbers
    starting from Fn and Fnn to stop (exclusive).
    generator.send(value) sets and returns the next number as value."""
    ### END SOLUTION
    while Fn < stop:
        value = yield Fn
        if value is not None:
            Fnn = value  # set next number to the value of yield expression
        Fn, Fnn = Fnn, Fnn + Fn


fibonacci_generator = fibonacci_sequence(0, 1, 5)
print(next(fibonacci_generator))
print(fibonacci_generator.send(2))
for fib in fibonacci_generator:
    print(fib)
Lab 5
Manim (optional)
Lecture 6
Decorator