Functional Programming

Recursion¶

To motivate the idea of programming using functions, consider the problem of computing the greatest common divisor:

def gcd(a, b):
    ### BEGIN SOLUTION
    return gcd(b, a % b) if b else abs(a)
    ### END SOLUTION


print(gcd(3 * 5, 5 * 7))

# tests
a, b = 3*5, 5*7
assert gcd(a, b) == gcd(a, -b) == gcd(-a, b) == 5
assert gcd(10**10, 10**10 + 1) == 1

One may implement Definition 1 directly using a for loop as follows:

def gcd(a, b):
    if a and b:
        for d in range(min(abs(a), abs(b)), 0, -1):
            if a % d == b % d == 0:
                return d
    return abs(a) or abs(b)


print(gcd(3 * 5, 5 * 7))

Unfortunately, the implementation is inefficient. It will take a long time to run the following test case:

if input('Run? [Y/n]').lower() != 'n':
    assert gcd(10**10, 10**10 + 1) == 1

Run? [Y/n] n

A more efficient way to compute gcd is as follows:

Proof

The base case holds trivially and $\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a)$ , so it suffices to show that any common factor of $a$ and $b$ must divide $r:=a\operatorname{mod}b$ , if $b\neq 0$ . To this end, suppose $c$ is the common factor. Then, for some integers $q_0, q_1, q_2$ :

\begin{align} r &\stackrel{\text{(a)}}= \underbrace{a}_{\stackrel{\text{(b)}}=q_1 c} - \underbrace{b}_{\stackrel{\text{(c)}}=q_2 c} q_0\\ &= (q_1-q_2 q_0) c \end{align}

(2)

which is divisible by $c$ as desired. (Can you explain the equalities $\text{(a)--(c)}$ ?)

How to implement (1)? Can we define gcd using gcd?

def gcd(a, b):
    return gcd(a % b, b)


print(gcd(3 * 5, 5 * 7))

Run? [Y/n]

Fetching long content....

Solution to Exercise 2

It is crucial to swap the arguments to ensure a strict reduction in the size of the problem. Additionally, the base case gcd(a, 0) must be handled properly to terminate the recursive call correctly. For example, the following implementation can result in an infinite loop:

def gcd(a, b):
    return gcd(b, a % b if b else a)

This occurs because gcd(a, 0) returns gcd(0, a), which in turn calls gcd(a, 0) again, i.e., there is no reduction in the size of the problem.

%%hermes --no-context
Using Euclidean algorithm for gcd, explain in one paragraph or two how to come 
up with a recursion that solves a problem by divide-and-conquer.

Loading...

↻ Session: main (ACP: ffb54f4c-e3e…)

See Also

Coming up with divide-and-conquer recursion follows two key steps. First, find an inductive reduction: show that solving the problem on a smaller instance gives you the answer to the original problem. In the Euclidean algorithm, the critical insight is gcd(a, b) = gcd(b, a mod b) — the GCD of two numbers equals the GCD of the smaller number and the remainder. This reduces a large problem to a strictly smaller one (since a mod b < b), guaranteeing progress toward a base case. Second, identify the base case where the problem is trivially solvable: gcd(a, 0) = a. Once you have the reduction rule and the base case, you just write them down directly as the recursive step and the termination condition.

The general recipe for any divide-and-conquer recursion is the same: (1) ask “can I express this problem in terms of a smaller subproblem of the same kind?” — that’s your recursive step; and (2) ask “when is the problem small enough to solve immediately?” — that’s your base case. The Euclidean algorithm works because the modular reduction shrinks the input monotonically, so the recursion is guaranteed to terminate.

Recursion vs Iteration¶

Is recursion always better than iteration?

Consider computing the Fibonacci number of order $n$ , which is defined in a recursive manner by the following recurrence relation:^[2]

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}

(3)

%%hermes --no-context
Describe what the fibonacci number is in one sentence and list three most
important applications of the Fibonacci number in bullet points.

Loading...

↻ Session: main (ACP: ffb54f4c-e3e…)

See Also

Fibonacci numbers are a sequence where each number is the sum of the two preceding ones, starting from 0 and 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Three important applications:

Algorithm analysis & complexity — Fibonacci numbers appear in the worst-case analysis of algorithms like Fibonacci heaps, divide-and-conquer recurrences, and the worst-case input for naive recursive algorithms (making it the canonical example for teaching recursion vs. memoization).
Natural phenomena & modeling — They describe growth patterns found throughout biology: phyllotaxis (leaf arrangement), branching trees, branching in coral reefs, and the spirals in sunflower seeds and pinecones.
Financial analysis & trading — Fibonacci retracement and extension levels are widely used in technical analysis to predict potential support and resistance price levels in markets.

The following function fibonacci(n) implements $F_n$ naturally as a recursion:

%%pytutor
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))

Loading...

# Assign n the appropriate value
### BEGIN SOLUTION
n = 35
### END SOLUTION
n

35

%%timeit -n 1 -r 1
fibonacci(n)

# hidden tests
### BEGIN HIDDEN TESTS
n < 40
### END HIDDEN TESTS

True

Is the recursion efficient?

As a comparison, the following computes the Fibonacci number using a while loop instead of a recursion.

%%pytutor
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)

Loading...

# Assign n the appropriate value
### BEGIN SOLUTION
n = 340000
### END SOLUTION
n

%%timeit -n 1 -r 1
fibonacci_iteration(n)

1.13 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

# hidden tests
### BEGIN HIDDEN TESTS
n > 3e5
### END HIDDEN TESTS

True

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)

fibonacci(5)
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)

5

Solution to Exercise 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).

Setting performance considerations aside, do we really need recursion?

Indeed, we can always convert a recursion to an iteration that is at least as efficient. (Why?)^[3]

%%pytutor
def gcd_iteration(a, b):
    ### BEGIN SOLUTION
    while b:
        a, b = b, a % b
    return a
    ### END SOLUTION


gcd_iteration(3 * 5, 5 * 7)

Loading...

%%hermes --no-context
Explain in one paragraph what a tail recursion is and how to convert a tail
recursion to an iteration.

Loading...

↻ Session: main (ACP: ffb54f4c-e3e…)

See Also

Tail recursion occurs when a recursive call is the very last operation in a function — no further computation happens after the call returns, meaning the current stack frame holds nothing more to do and can be discarded. Because of this, a tail-recursive function can be converted directly into an iteration by replacing the function’s parameters with local variables and wrapping the body in a loop that updates those variables each iteration instead of making a recursive call. The key pattern is: (1) initialize the loop variables from the original arguments (often including an accumulator that carries the intermediate result), (2) repeat the body’s computation in a while loop, updating the variables to what would have been the next recursive call’s arguments, and (3) return the accumulator when the base case is reached. This transformation preserves the logic while eliminating the call-stack growth that ordinary recursion incurs.

%%hermes --no-context
Explain in one paragraph how non-tail recursive functions can be significantly
slower than their iterative counterparts.

See Also

Non-tail recursive functions can be significantly slower than their iterative counterparts because each recursive call pushes a new stack frame onto the call stack — a bookkeeping operation that saves local variables, return addresses, and registers before jumping to the next call. For a function that recurses N times, this means N stack allocations and N deallocations on the way back, each incurring memory access overhead that an iterative loop completely avoids by reusing the same stack frame throughout. Additionally, the deep chain of nested calls can exhaust the stack, causing stack overflow, while also evicting instruction-cache entries and preventing the CPU branch predictor from settling into a stable pattern — whereas a tight loop runs in-place with minimal overhead, excellent cache locality, and predictable branching.

Global Variables¶

Suppose our task is to print the entire sequence of Fibonacci numbers up to certain order such as:

for n in range(10):
    print(fibonacci_iteration(n))

Solution to Exercise 7

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

How to avoid redundant computations?

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

%%pytutor
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():
    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()

Loading...

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?

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


next_fibonacci()

Loading...

UnboundLocalError is raised (as opposed 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.

Consider rewriting the for loop as a while loop:

%%pytutor
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()

Loading...

Solution to Exercise 8

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.

%%pytutor
_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()

Loading...

Closure¶

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

We can use nested functions and nonlocal variables.

def create_fibonacci(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 = create_fibonacci(0, 1)
n = 0
while n < 5:
    print(next_fibonacci())
    n += 1
print_fibonacci_state()

0
1
1
2
3
States:
        Next Fibonacci number      = 5
        Next next Fibonacci number = 8
        Next order                 = 5

The state variables Fn, Fnn, and n are now encapsulated, meaning they are contained within the scope of the create_fibonacci function, i.e.,

they are not exposed globally, unlike the global variables, but
they are accessible by the inner functions of create_fibonacci.

The encapsulation allows us to create multiple Fibonacci sequences with different base cases independently without interfering with each others:

usual_fib = create_fibonacci(0, 1)
cs1302_fib = create_fibonacci("cs", "1302")
for n in range(3):
    print(usual_fib[0]())
    usual_fib[1]()
    print(cs1302_fib[0]())
    cs1302_fib[1]()

0
States:
        Next Fibonacci number      = 1
        Next next Fibonacci number = 1
        Next order                 = 1
cs
States:
        Next Fibonacci number      = 1302
        Next next Fibonacci number = cs1302
        Next order                 = 1
1
States:
        Next Fibonacci number      = 1
        Next next Fibonacci number = 2
        Next order                 = 2
1302
States:
        Next Fibonacci number      = cs1302
        Next next Fibonacci number = 1302cs1302
        Next order                 = 2
1
States:
        Next Fibonacci number      = 2
        Next next Fibonacci number = 3
        Next order                 = 3
cs1302
States:
        Next Fibonacci number      = 1302cs1302
        Next next Fibonacci number = cs13021302cs1302
        Next order                 = 3

next_fibonacci and print_fibonacci_state are local functions of create_fibonacci:

Local functions can access (capture) the other local variables of create_fibonacci by forming the so-called closures. Each local function has an attribute named __closure__ that stores the captured local variables.
Similar to the global statement, a nonlocal statement is needed for assigning non-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)

closure of  next_fibonacci
    <cell at 0x7baf05dd1a20: int object at 0x60e93b870990> content: 5
    <cell at 0x7baf05dd37c0: int object at 0x60e93b8709f0> content: 8
    <cell at 0x7baf05dd3100: int object at 0x60e93b870990> content: 5
closure of  print_fibonacci_state
    <cell at 0x7baf05dd1a20: int object at 0x60e93b870990> content: 5
    <cell at 0x7baf05dd37c0: int object at 0x60e93b8709f0> content: 8
    <cell at 0x7baf05dd3100: int object at 0x60e93b870990> content: 5

Lexical scoping can sometimes be counter-intuitive:

def foo():
    return x


def bar():
    x = "dynamically scoped"
    # NOT the same as:
    # return x
    return foo()  


x = "lexically scoped"
bar()

'lexically scoped'

Try re-executing the above code after uncommenting the line # return x. Even though foo() returns x, the line return foo() is not the same as return x, i.e., one cannot simply substitute foo() by x.

%%hermes --no-context
Explain in one paragraph the differences between lexical scoping and dynamic
scoping, and why Python implements the prior.

Loading...

↻ Session: main (ACP: ffb54f4c-e3e…)

See Also

Lexical scoping resolves a variable name by looking up the chain of textually enclosing blocks — the binding is determined by where the code is written and is fixed at compile time. Dynamic scoping resolves names by walking the call stack at runtime — a free variable looks through the caller’s local scope, then the caller’s caller, making the same identifier depend on who invoked the function rather than where it was defined. Python implements lexical scoping because it makes code behavior predictable: you can determine a name’s binding just by reading the source layout without tracing every possible call path, which enables static analysis, reliable IDE tooling, clear data-flow reasoning, and avoids the subtle bugs that arise when unrelated functions unintentionally share caller-level state.

Lexical scoping is a powerful concept that can be leveraged to implement object-oriented programming. For example, we can rewrite create_fibonacci to return a Fibonacci object as shown below:

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

    def self():  # make the return object callable to replace
        print(
            """States:
        Next Fibonacci number      = {}
        Next next Fibonacci number = {}
        Next order                 = {}""".format(
                Fn, Fnn, n
            )
        )

    n = 0

    self.next = next  # add next as an attribute of self
    return self       # to be returned


fib = create_fibonacci(0, 1)
n = 0
while n < 5:
    print(fib.next())
    n += 1
fib()

0
1
1
2
3
States:
        Next Fibonacci number      = 5
        Next next Fibonacci number = 8
        Next order                 = 5

The create_fibonacci function returns the self function, which has access to the next function and other internal states of the create_fibonacci function. To create multiple Fibonacci objects:

usual_fib = create_fibonacci(0, 1)
cs1302_fib = create_fibonacci("cs", "1302")
for n in range(3):
    print(usual_fib.next())
    usual_fib()
    print(cs1302_fib.next())
    cs1302_fib()

0
States:
        Next Fibonacci number      = 1
        Next next Fibonacci number = 1
        Next order                 = 1
cs
States:
        Next Fibonacci number      = 1302
        Next next Fibonacci number = cs1302
        Next order                 = 1
1
States:
        Next Fibonacci number      = 1
        Next next Fibonacci number = 2
        Next order                 = 2
1302
States:
        Next Fibonacci number      = cs1302
        Next next Fibonacci number = 1302cs1302
        Next order                 = 2
1
States:
        Next Fibonacci number      = 2
        Next next Fibonacci number = 3
        Next order                 = 3
cs1302
States:
        Next Fibonacci number      = 1302cs1302
        Next next Fibonacci number = cs13021302cs1302
        Next order                 = 3

As the above code shows, closures enable an object-oriented programming approach by allowing the creation of objects that share methods but maintain possibly distinct attribute values.

%%hermes --no-context
Explain in one paragraph the importance of closures in programming and why they
are called closures.

Loading...

↻ Session: main (ACP: ffb54f4c-e3e…)

A closure is a function that captures and retains access to the variables in its surrounding scope even after that scope has finished executing. They are called “closures” because the function closes over — binds to and carries with it — the environment in which it was created, preserving those external bindings rather than letting them go out of scope. Closures are important because they enable functions to carry private state without global variables, support powerful patterns like callbacks, partial application, decorators, and event handlers, and provide a clean bridge between data and behavior: a closure bundles a computation with the data it needs into a single, first-class value that can be passed around, stored, and invoked later, all while keeping that data encapsulated and inaccessible from the outside.

Solution to Exercise 9 #

When rewriting a for loop as map() or filter(), evaluate:

map(func, iterable) applies func to each element, producing a new iterator (lazy evaluation).
filter(predicate, iterable) keeps only elements where predicate is true.
The functional version is more concise for simple transformations, but a for loop is more readable when the logic involves multiple steps, complex conditions, or side effects like printing.
Example: [x**2 for x in range(10)] (list comprehension) often strikes the best balance between readability and conciseness.

%%hermes --no-context
How to define static variables in Python?

Loading...

↻ Session: main (ACP: ffb54f4c-e3e…)

See Also

Python doesn’t have a static keyword for local variables, but you can achieve the same effect — a variable that persists across calls while staying local to one function — using a few common approaches:

1. Function attributes (most common and explicit)

def counter():
    counter.n += 1
    return counter.n

counter.n = 0  # initialise

2. Mutable default argument

def counter(n=[0]):
    n[0] += 1
    return n[0]

This works because the default list object is created once at function definition time and reused on every call. It’s a well-known Python idiom but can look like a bug to those unfamiliar with it.

3. Closure with a nonlocal variable

def make_counter():
    n = 0
    def counter():
        nonlocal n
        n += 1
        return n
    return counter

counter = make_counter()

4. Using a class

class Counter:
    n = 0
    @classmethod
    def count(cls):
        cls.n += 1
        return cls.n

The function attribute approach is generally preferred because it’s the most Pythonic, readable, and keeps everything attached to the function itself without workarounds.

%%hermes --no-context
Why is closure as a thread-safe alternative to static variables?

Loading...

↻ Session: main (ACP: ffb54f4c-e3e…)

See Also

A closure isn’t thread-safe because it has built-in locking — it’s thread-safe because it eliminates shared state entirely. With a static variable, every thread calling the same function shares one piece of mutable data, requiring locks or atomics to avoid race conditions. With a closure, you create a factory function that returns a new closure for each consumer — each closure captures its own private copy of the enclosed variables. If every thread gets its own closure instance, there is no shared mutable state to contend over, so no synchronization is needed. This is the core principle of functional programming: state is isolated inside independent objects rather than pooled globally, making the program inherently free of data races without any locking overhead.

Solution to Exercise 10 #

Using functools.reduce() to find the maximum:

from functools import reduce
my_max = reduce(lambda a, b: a if a > b else b, numbers)

reduce takes a binary function and applies it cumulatively to accumulate a single result.
max() is the better choice in practice because:
- It is more readable and expresses the intent directly.
- It is implemented in C and optimized for performance.
- reduce with lambda is harder to debug and less Pythonic.
As Python’s documentation notes, reduce was moved to functools precisely because explicit loops are often clearer.

Functional Programming

Abstract¶

Recursion¶

Recursion vs Iteration¶

Global Variables¶

Closure¶