Skip to content

Higher-Order Functions and Recursion

Summary

This chapter covers two powerful programming paradigms: higher-order functions and recursion. Students will learn to write lambda functions, use map/filter/reduce, and compose functions. The chapter then introduces recursive thinking, including identifying base and recursive cases, tracing the call stack, and comparing recursive vs iterative solutions. These techniques are essential for elegant problem solving.

Concepts Covered

This chapter covers the following 16 concepts from the learning graph:

  1. Function Documentation
  2. Helper Functions
  3. Main Function Pattern
  4. Lambda Functions
  5. Higher-Order Functions
  6. Map Function
  7. Filter Function
  8. Reduce Function
  9. Function Composition
  10. Recursion
  11. Base Case
  12. Recursive Case
  13. Recursive Call Stack
  14. Stack Overflow
  15. Recursion vs Iteration
  16. Recursive Patterns

Prerequisites

This chapter builds on concepts from:

Monty says: Let's code this!

Monty Welcome back, coders! In Chapter 6 you learned to build your own functions -- the basic building blocks of modular code. Now we're going to level up. In this chapter, you'll discover that functions in Python are incredibly flexible: you can pass them around like any other value, combine them like building blocks, and even have them call themselves. That last part -- recursion -- might bend your brain a little, but trust me, it's one of the most elegant ideas in all of computer science. Let's do this!

Writing Professional Functions

Before we dive into the fancy stuff, let's make sure our functions are clean, well-organized, and professional. Two important practices -- function documentation and the use of helper functions -- will make your code easier to read, debug, and share.

Function Documentation

Function documentation (also called a docstring) is a description you place right inside your function to explain what it does. In Python, you write it as a triple-quoted string immediately after the def line:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def calculate_area(length, width):
    """Calculate the area of a rectangle.

    Args:
        length: The length of the rectangle (must be positive).
        width: The width of the rectangle (must be positive).

    Returns:
        The area as a float.
    """
    return length * width

Why bother? Imagine you wrote this function six months ago. Without a docstring, you'd have to re-read all the code to remember what it does. With a docstring, the explanation is right there. Even better, Python's built-in help() function can display your docstring:

1
help(calculate_area)

Good docstrings answer three questions:

  • What does this function do?
  • What arguments does it take?
  • What does it return?

Think of a docstring like a label on a box. You could open the box to figure out what's inside, but a label is way faster.

Helper Functions

A helper function is a small, focused function that does one specific job to support a larger function. Instead of writing one giant function that does everything, you break the work into smaller pieces.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def is_even(n):
    """Return True if n is even."""
    return n % 2 == 0

def count_evens(numbers):
    """Count how many even numbers are in the list."""
    count = 0
    for num in numbers:
        if is_even(num):
            count += 1
    return count

Here, is_even() is a helper function. It handles one tiny task -- checking if a number is even -- so that count_evens() stays clean and readable. Helper functions follow the principle of decomposition from Chapter 1: break big problems into smaller pieces.

Benefits of helper functions:

  • Readability -- Your main logic reads almost like English
  • Reusability -- You can use is_even() anywhere else in your program
  • Testability -- You can test each small function independently

The Main Function Pattern

In many Python programs, you'll see a common structure called the main function pattern. Instead of scattering code throughout your file, you wrap the primary logic inside a main() function and then call it at the bottom:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def greet(name):
    """Helper: return a greeting string."""
    return f"Hello, {name}! Welcome to Python."

def main():
    """Main function: runs the program."""
    user_name = input("What's your name? ")
    message = greet(user_name)
    print(message)

# This line runs main() only when the file is executed directly
if __name__ == "__main__":
    main()

The mysterious if __name__ == "__main__": line tells Python: "Only run main() if this file is being executed directly, not when it's imported by another file." This pattern keeps your code organized and reusable. You'll see it in almost every professional Python project.

Here's why the main function pattern matters:

Benefit Explanation
Organization All top-level logic is in one place
Reusability Other files can import your helpers without running main()
Testing You can test functions individually without triggering the full program
Readability Anyone reading your code knows where to start

Lambda Functions: Functions in a Single Line

Sometimes you need a quick, throwaway function that's so short it doesn't deserve a full name. Enter the lambda function -- a way to define a tiny, anonymous function in a single line.

1
2
3
4
5
6
7
8
# Regular function
def double(x):
    return x * 2

# Equivalent lambda function
double = lambda x: x * 2

print(double(5))  # Output: 10

The syntax is: lambda arguments: expression. The lambda takes the arguments, evaluates the expression, and returns the result. No def, no return, no name required.

Here are a few more examples:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Add two numbers
add = lambda a, b: a + b
print(add(3, 7))  # Output: 10

# Check if a number is positive
is_positive = lambda n: n > 0
print(is_positive(-3))  # Output: False

# Get the last character of a string
last_char = lambda s: s[-1]
print(last_char("Python"))  # Output: n

Lambda functions shine when you need a quick function to pass as an argument to another function -- which brings us to one of the most powerful ideas in this chapter.

Monty says: You've got this!

Monty Think of a lambda function like a sticky note. A regular function is a full letter you write, sign, and file away. A lambda is a quick note you scribble and hand to someone. Both communicate a message, but you'd use the sticky note when you need something fast and disposable.

Higher-Order Functions

Here's where things get really interesting. In Python, functions are first-class objects. That means you can store them in variables, put them in lists, and -- most importantly -- pass them as arguments to other functions or return them as results.

A higher-order function is any function that either:

  1. Takes another function as an argument, OR
  2. Returns a function as its result

You've already seen hints of this. When you pass lambda x: x * 2 to another function, that other function is a higher-order function. Let's see a concrete example:

1
2
3
4
5
6
def apply_operation(func, value):
    """Apply a function to a value and return the result."""
    return func(value)

result = apply_operation(lambda x: x ** 2, 5)
print(result)  # Output: 25

Here, apply_operation is a higher-order function because it takes func as a parameter. We passed in a lambda that squares a number, and it applied that operation to 5. Neat!

Why is this useful? It lets you write general-purpose functions that can do different things depending on what function you pass in. Same tool, different attachments -- like a power drill with interchangeable bits.

Python comes with three built-in higher-order functions that you'll use all the time: map(), filter(), and reduce().

Diagram: Higher-Order Functions Flow

Higher-Order Functions Flow Diagram

Type: diagram sim-id: higher-order-functions-flow
Library: p5.js
Status: Specified

Bloom Level: Understand (L2) Bloom Verb: explain, classify

Learning Objective: Students will be able to explain what makes a function "higher-order" and classify examples as higher-order or regular functions.

Layout: - Top section: Title "Higher-Order Functions" - Center: A visual pipeline showing a function (represented as a machine/box) receiving two inputs -- a regular value (shown as a number ball) and a function (shown as a gear/tool icon) - Three lanes below showing map, filter, and reduce as specific examples of higher-order functions - Each lane shows: input list -> function being applied -> output

Interactive elements: - Hover over each lane (map, filter, reduce) to see a brief description and example - Click on a lane to see an animated demonstration of how data flows through that higher-order function - Toggle between "Visual Mode" (animated icons) and "Code Mode" (Python syntax)

Visual elements: - Regular values shown as colored number balls - Functions shown as gears or tool icons - Arrows showing data flow direction - Map lane: shows each input ball being transformed into a different colored ball - Filter lane: shows some balls passing through a gate while others are blocked - Reduce lane: shows multiple balls being combined into a single result ball

Color scheme: - Map: blue tones - Filter: green tones - Reduce: orange tones - Input values: light gray - Output values: bright colors matching the operation

Responsive: Canvas resizes with window; lanes stack vertically on narrow screens

Instructional Rationale: A visual pipeline metaphor makes the abstract concept of "passing a function to a function" concrete. Showing map, filter, and reduce as parallel examples helps students see the common pattern (input + function = output) while distinguishing each operation's unique behavior.

The Map Function

The map function applies a given function to every item in a list (or other iterable) and returns the results. Think of it like a factory assembly line: every item on the conveyor belt gets the same transformation applied.

1
2
3
numbers = [1, 2, 3, 4, 5]
doubled = list(map(lambda x: x * 2, numbers))
print(doubled)  # Output: [2, 4, 6, 8, 10]

Here's what happened step by step:

  1. map() took the lambda function and the list numbers
  2. It applied lambda x: x * 2 to each element: 1 becomes 2, 2 becomes 4, 3 becomes 6...
  3. list() converted the result into a list

You can use map() with any function, not just lambdas:

1
2
3
4
5
6
7
def to_uppercase(s):
    """Convert a string to uppercase."""
    return s.upper()

names = ["alice", "bob", "charlie"]
loud_names = list(map(to_uppercase, names))
print(loud_names)  # Output: ['ALICE', 'BOB', 'CHARLIE']

The Filter Function

The filter function tests every item in a list with a function that returns True or False, and keeps only the items that pass the test. It's like a bouncer at a club -- only the items that meet the criteria get in.

1
2
3
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
evens = list(filter(lambda x: x % 2 == 0, numbers))
print(evens)  # Output: [2, 4, 6, 8, 10]

The lambda lambda x: x % 2 == 0 returns True for even numbers and False for odd ones. filter() keeps only the True items.

Here's another example -- filtering strings by length:

1
2
3
words = ["hi", "hello", "hey", "howdy", "yo"]
long_words = list(filter(lambda w: len(w) > 2, words))
print(long_words)  # Output: ['hello', 'hey', 'howdy']

The Reduce Function

The reduce function takes a list of items and combines them down to a single value by repeatedly applying a function. Think of it like folding a long piece of paper in half, again and again, until you end up with one thick square.

Unlike map() and filter(), reduce() isn't built-in -- you need to import it:

1
2
3
4
5
from functools import reduce

numbers = [1, 2, 3, 4, 5]
total = reduce(lambda a, b: a + b, numbers)
print(total)  # Output: 15

Here's how reduce processes this step by step:

Step a b Result
1 1 2 3
2 3 3 6
3 6 4 10
4 10 5 15

It starts with the first two elements (1 and 2), adds them to get 3. Then it takes that 3 and adds the next element (3) to get 6. And so on, until every element has been folded in.

Here's a comparison of all three functions:

Function What It Does Input Output Analogy
map() Transforms each item List + function New list (same length) Assembly line
filter() Keeps items that pass a test List + function New list (same or shorter) Bouncer at a club
reduce() Combines all items into one List + function Single value Folding paper

Monty says: Let's debug this together!

Monty A common mistake is forgetting to wrap map() and filter() with list(). In Python 3, these functions return iterator objects, not lists. If you just write map(func, data) without list(), you'll get something like <map object at 0x...> instead of the actual values. Always wrap with list() when you want to see the results!

Diagram: Map Filter Reduce Pipeline

Map Filter Reduce Pipeline MicroSim

Type: microsim sim-id: map-filter-reduce-pipeline
Library: p5.js
Status: Specified

Bloom Level: Apply (L3) Bloom Verb: apply, demonstrate

Learning Objective: Students will be able to chain map, filter, and reduce operations on a list and predict the output at each stage.

Layout: - Top: An input conveyor belt with numbered balls (the input list) - Three processing stations arranged left to right: MAP, FILTER, REDUCE - Between each station, a conveyor belt shows intermediate results - Bottom: Final output display

Interactive controls: - Input field to enter a comma-separated list of numbers (default: 1,2,3,4,5,6,7,8,9,10) - Dropdown to select map operation: "double", "square", "negate", "add 10" - Dropdown to select filter condition: "even", "odd", "greater than 5", "positive" - Dropdown to select reduce operation: "sum", "product", "max", "min" - "Run Pipeline" button: Animates the data flowing through all three stages - "Step" button: Advance one item at a time through the pipeline - "Reset" button: Clear and start over

Visual elements: - Numbered balls on conveyor belts - MAP station: balls change color/number as they're transformed - FILTER station: a gate that opens for passing items and shows rejected items falling off - REDUCE station: balls merge together into one final ball - Each station shows the Python code equivalent below it - Running total/status shown at each stage

Animation: - Smooth ball movement along conveyor belts - Transformation animation at MAP (ball morphs) - Accept/reject animation at FILTER (gate opens or ball drops) - Merge animation at REDUCE (two balls combine into one)

Color scheme: Industrial/factory theme with steel grays, colored balls, green for accepted, red for rejected

Responsive: Canvas scales with window; stations may stack vertically on narrow screens

Instructional Rationale: The factory/pipeline metaphor makes the abstract chaining of higher-order functions tangible. Step-by-step animation lets students predict what happens next before seeing the result, which supports active learning at the Apply level. Customizable inputs encourage experimentation.

Function Composition

Function composition means combining two or more functions so that the output of one becomes the input of the next. It's like an assembly line where the product passes through multiple stations, each one adding or changing something.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def add_tax(price):
    """Add 8% sales tax."""
    return price * 1.08

def apply_discount(price):
    """Apply a 20% discount."""
    return price * 0.80

def format_price(price):
    """Format as a dollar string."""
    return f"${price:.2f}"

# Compose the functions: discount first, then tax, then format
original_price = 100
final = format_price(add_tax(apply_discount(original_price)))
print(final)  # Output: $86.40

Notice how we read the composition from the inside out: first apply_discount(100) returns 80, then add_tax(80) returns 86.4, then format_price(86.4) returns "$86.40". Each function takes the previous function's result as its input.

You can also write a general-purpose compose function:

1
2
3
4
5
6
7
def compose(f, g):
    """Return a new function that applies g first, then f."""
    return lambda x: f(g(x))

# Create a composed function
discount_then_tax = compose(add_tax, apply_discount)
print(discount_then_tax(100))  # Output: 86.4

Function composition is everywhere in programming. When you chain operations together -- like transforming data, then filtering it, then formatting it -- you're composing functions. It's a key pattern in writing clean, modular code.

Recursion: Functions That Call Themselves

Now for the mind-bending part. What if a function could call itself? That's recursion, and it's one of the most powerful (and initially confusing) ideas in computer science.

Monty says: You've got this!

Monty Recursion can feel weird at first -- and that's totally normal! Even experienced programmers had to wrap their heads around it. Think of Russian nesting dolls (matryoshkas): you open one doll and find a smaller doll inside, open that one and find an even smaller doll, and so on until you reach the tiniest doll that can't be opened. That's recursion! Each doll "contains" a smaller version of itself, and the tiniest doll is where the process stops.

Here's the simplest possible recursive function:

1
2
3
4
5
6
7
8
9
def countdown(n):
    """Count down from n to 1, then print 'Go!'"""
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)

countdown(3)

Output:

1
2
3
4
3
2
1
Go!

The function countdown() calls itself with a smaller number each time. When n reaches 0, it stops. This brings us to the two essential ingredients of every recursive function.

Base Case

The base case is the condition that stops the recursion. Without it, the function would call itself forever (spoiler: that's bad). The base case is the "tiniest nesting doll" -- the simplest version of the problem that you can solve directly without any more recursive calls.

In our countdown example, the base case is if n == 0: print("Go!"). When we reach zero, we don't call countdown() again. We just print and stop.

Recursive Case

The recursive case is the part where the function calls itself with a smaller or simpler version of the problem. Each recursive call should move you closer to the base case.

In our countdown, the recursive case is countdown(n - 1). Each call reduces n by 1, so we're guaranteed to eventually reach 0 (the base case).

Every recursive function must have:

Component What It Does What Happens Without It
Base case Stops the recursion Infinite recursion (crash!)
Recursive case Makes the problem smaller and calls itself Function never does useful work
Progress toward base case Ensures we eventually stop Infinite recursion (crash!)

Classic Example: Factorial

The factorial of a number (n) (written (n!)) is the product of all positive integers from 1 to (n):

[ n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 ]

For example, (5! = 5 \times 4 \times 3 \times 2 \times 1 = 120).

Notice something interesting: (5! = 5 \times 4!). And (4! = 4 \times 3!). Each factorial is defined in terms of a smaller factorial. That's a perfect fit for recursion!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def factorial(n):
    """Calculate n! recursively.

    Base case: 0! = 1
    Recursive case: n! = n * (n-1)!
    """
    if n == 0:
        return 1          # Base case
    else:
        return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # Output: 120

Let's trace through factorial(5):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
factorial(5) = 5 * factorial(4)
             = 5 * (4 * factorial(3))
             = 5 * (4 * (3 * factorial(2)))
             = 5 * (4 * (3 * (2 * factorial(1))))
             = 5 * (4 * (3 * (2 * (1 * factorial(0)))))
             = 5 * (4 * (3 * (2 * (1 * 1))))
             = 5 * (4 * (3 * (2 * 1)))
             = 5 * (4 * (3 * 2))
             = 5 * (4 * 6)
             = 5 * 24
             = 120

The function "unwinds" outward until it hits the base case, then the results cascade back, multiplying at each level.

Diagram: Factorial Recursion Tree

Factorial Recursion Tree MicroSim

Type: microsim sim-id: factorial-recursion-tree
Library: p5.js
Status: Specified

Bloom Level: Understand (L2) Bloom Verb: trace, explain

Learning Objective: Students will be able to trace through recursive factorial calls, identify the base case and recursive case, and explain how the return values cascade back up.

Layout: - Top: Input slider for n (range 1 to 8, default 5) - Center: A vertical tree showing each recursive call as a node - Each node shows: the function call (e.g., "factorial(5)"), the computation (e.g., "5 * factorial(4)"), and the return value once computed - Arrows connecting parent calls to child calls going down - Return value arrows going back up - Bottom: Final result display

Interactive controls: - Slider to set n (1-8) - "Step Forward" button: Reveals one level of recursion at a time (going down) - "Step Return" button: After reaching the base case, shows return values cascading up one at a time - "Auto Play" button: Animates the full trace automatically - "Reset" button: Clear and start over - Speed slider for auto play

Visual elements: - Each recursive call shown as a rounded rectangle node - Nodes appear one at a time as you step forward (building the call chain downward) - Base case node highlighted in green with a star icon - Recursive case nodes in blue - When stepping return: each node fills with its computed return value in gold - Arrows animate to show data flow direction (down for calls, up for returns) - Current active node is highlighted with a pulsing border

Animation sequence: 1. Start with factorial(n) node at top 2. Each step adds a new child node below: factorial(n-1) 3. When base case is reached, node turns green 4. Return phase: each node computes its value and passes it up 5. Final result shown at the top in large text

Color scheme: Blue nodes for recursive calls, green for base case, gold for computed values

Responsive: Tree repositions based on canvas width; nodes scale for smaller screens

Instructional Rationale: Step-by-step trace visualization makes the "unwinding" and "rewinding" nature of recursion concrete. Students can pause at each step to predict what happens next, reinforcing understanding of base and recursive cases. The visual tree structure mirrors how recursion is often explained on paper, creating a bridge between the code and the mental model.

The Recursive Call Stack

When a function calls itself, Python doesn't throw away the current call. Instead, it pauses the current call and stacks a new one on top. This data structure is called the recursive call stack (or just "the call stack").

Imagine a stack of cafeteria trays. Each time you make a recursive call, a new tray goes on top. When a call finishes (returns), its tray gets removed. The previous call resumes where it left off.

Here's what the call stack looks like for factorial(4):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Step 1: [factorial(4)] -- calls factorial(3)
Step 2: [factorial(4), factorial(3)] -- calls factorial(2)
Step 3: [factorial(4), factorial(3), factorial(2)] -- calls factorial(1)
Step 4: [factorial(4), factorial(3), factorial(2), factorial(1)] -- calls factorial(0)
Step 5: [factorial(4), factorial(3), factorial(2), factorial(1), factorial(0)]
        -- base case reached! Returns 1
Step 6: [factorial(4), factorial(3), factorial(2), factorial(1)]
        -- returns 1 * 1 = 1
Step 7: [factorial(4), factorial(3), factorial(2)]
        -- returns 2 * 1 = 2
Step 8: [factorial(4), factorial(3)]
        -- returns 3 * 2 = 6
Step 9: [factorial(4)]
        -- returns 4 * 6 = 24

Each frame on the call stack holds its own local variables. The n in factorial(4) is 4, the n in factorial(3) is 3, and so on. They don't interfere with each other.

Diagram: Recursive Call Stack Visualizer

Recursive Call Stack Visualizer MicroSim

Type: microsim sim-id: recursive-call-stack
Library: p5.js
Status: Specified

Bloom Level: Analyze (L4) Bloom Verb: trace, differentiate

Learning Objective: Students will be able to trace the call stack during recursive execution, identify when frames are pushed and popped, and determine the value of local variables at any point during execution.

Layout: - Left panel (60%): Code display showing the recursive function with line-by-line highlighting - Right panel (40%): Visual call stack showing frames stacking up and down - Bottom: Controls and status bar

Code display (left panel): - Shows the factorial function code with line numbers - Current executing line is highlighted in yellow - A dropdown to switch between "Factorial", "Fibonacci", and "Countdown" examples

Call stack display (right panel): - Stack frames shown as rectangles stacking upward (like cafeteria trays) - Each frame displays: - Function name and argument (e.g., "factorial(3)") - Local variable values (e.g., "n = 3") - Return value (shown when the frame completes, in gold) - New frames animate sliding in from the right onto the top of the stack - Completed frames animate sliding out to the left - Base case frame is highlighted in green - Current active frame has a pulsing yellow border

Interactive controls: - Function selector dropdown: "Factorial", "Fibonacci", "Countdown" - Input field for the argument (e.g., n = 5) - "Step Into" button: Execute the next line, pushing a new frame if it's a recursive call - "Step Return" button: Complete the current frame and pop it off the stack - "Auto Play" button: Animate the full execution at adjustable speed - "Reset" button: Return to starting state - Speed slider for auto play - Stack depth counter: "Stack depth: 3 / max 1000"

Visual elements: - Stack frames are 3D-looking rectangles with slight shadows - Pushing a frame: frame slides in from the right and settles on top - Popping a frame: frame lifts off, shows return value floating up to the frame below - Return value animation: gold number floats from child frame to parent frame - Line highlight in code panel syncs with stack operations - Stack depth indicator with color gradient (green = safe, yellow = getting deep, red = nearing overflow)

Color scheme: - Active frame: yellow border - Waiting frames: blue - Base case frame: green - Return values: gold - Code highlight: yellow background

Responsive: Panels adjust width on resize; code panel may move above stack panel on narrow screens

Instructional Rationale: The call stack is the single most important mental model for understanding recursion. By syncing code execution with stack visualization, students can see the direct relationship between "this line of code executes" and "this frame is pushed/popped." The step-by-step controls let students pause and predict, which is critical for building accurate mental models at the Analyze level. Supporting multiple function examples (factorial, Fibonacci, countdown) helps students generalize the pattern.

Stack Overflow

What happens if you forget the base case? The function keeps calling itself forever, and the call stack grows taller and taller until Python runs out of memory. This crash is called a stack overflow.

1
2
3
4
5
6
def oops(n):
    """This function has no base case -- don't run this!"""
    return n * oops(n - 1)

# oops(5) would crash with:
# RecursionError: maximum recursion depth exceeded

Python has a default recursion limit of about 1,000 calls deep. If your function tries to go deeper than that, Python stops it and raises a RecursionError. This is a safety net to prevent your computer from freezing.

Monty says: Watch out!

Monty The two most common causes of stack overflow are: (1) forgetting the base case entirely, and (2) having a base case that's never actually reached (for example, checking if n == 0 but never decreasing n). Always ask yourself: "Does every recursive call move me closer to the base case?" If the answer is no, you've got an infinite recursion waiting to happen!

Common causes of stack overflow:

  • Missing base case -- The function never stops
  • Base case never reached -- The arguments don't progress toward the base case
  • Problem too large -- Even correct recursion on very deep problems can hit the limit

Recursion vs. Iteration

You might be thinking: "Can't I just use a loop instead?" Great question! Recursion vs. iteration is an important comparison. Many problems can be solved either way.

Here's factorial done both ways:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Recursive version
def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

# Iterative version (using a loop)
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Both give the same answer. So when should you use which?

Feature Recursion Iteration
Readability Can be more elegant and closer to the math definition Can be more straightforward for simple counting
Memory Uses more memory (call stack) Uses constant memory
Speed Can be slower due to function call overhead Generally faster
Best for Tree structures, divide-and-conquer, problems with natural recursive definitions Simple counting, accumulating results, large datasets
Risk Stack overflow if too deep Infinite loop if condition is wrong

In practice, many programmers use recursion when the problem naturally breaks into smaller subproblems (like tree traversal or parsing nested data), and iteration when they're just counting or accumulating values.

Recursive Patterns

Now that you understand the mechanics, let's look at some common recursive patterns that appear over and over in computer science.

Pattern 1: Linear Recursion (Factorial)

Each call makes exactly one recursive call. The call chain forms a straight line. Factorial is the classic example.

1
2
3
4
5
6
7
def sum_list(numbers):
    """Sum a list recursively."""
    if len(numbers) == 0:    # Base case: empty list
        return 0
    return numbers[0] + sum_list(numbers[1:])  # First element + sum of rest

print(sum_list([1, 2, 3, 4]))  # Output: 10

Pattern 2: Tree Recursion (Fibonacci)

Each call makes two or more recursive calls. The calls branch out like a tree. The Fibonacci sequence is the classic example.

The Fibonacci sequence starts with 0, 1, and each subsequent number is the sum of the two before it:

[ F(n) = F(n-1) + F(n-2) ]

So the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def fibonacci(n):
    """Return the nth Fibonacci number.

    Base cases: F(0) = 0, F(1) = 1
    Recursive case: F(n) = F(n-1) + F(n-2)
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))  # Output: 13

Be careful with tree recursion -- it can be very slow for large inputs because it recalculates the same values many times. fibonacci(30) makes over a million function calls! (You'll learn how to fix this with a technique called memoization in later chapters.)

Pattern 3: Divide and Conquer

The problem is split into smaller subproblems, each solved recursively, and then the results are combined. You'll see this in sorting algorithms like merge sort (Chapter 18).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def binary_search(sorted_list, target, low, high):
    """Search for target in a sorted list using recursion."""
    if low > high:
        return -1  # Base case: not found
    mid = (low + high) // 2
    if sorted_list[mid] == target:
        return mid  # Base case: found it!
    elif sorted_list[mid] < target:
        return binary_search(sorted_list, target, mid + 1, high)
    else:
        return binary_search(sorted_list, target, low, mid - 1)

Pattern 4: Accumulator Pattern

Pass an extra parameter that accumulates the result as you go. This can convert some recursive solutions into tail-recursive form:

1
2
3
4
5
6
7
def factorial_acc(n, accumulator=1):
    """Factorial with an accumulator parameter."""
    if n == 0:
        return accumulator
    return factorial_acc(n - 1, accumulator * n)

print(factorial_acc(5))  # Output: 120

Here's a summary of recursive patterns:

Pattern Calls per Step Shape Example
Linear 1 Straight line Factorial, sum of list
Tree 2+ Branching tree Fibonacci
Divide and conquer 2+ (on subsets) Balanced tree Binary search, merge sort
Accumulator 1 (with extra param) Straight line Tail-recursive factorial

Diagram: Fibonacci Tree Visualization

Fibonacci Tree Visualization MicroSim

Type: microsim sim-id: fibonacci-tree
Library: p5.js
Status: Specified

Bloom Level: Analyze (L4) Bloom Verb: compare, analyze

Learning Objective: Students will be able to trace Fibonacci recursion, identify redundant calculations in tree recursion, and compare the number of function calls for different input values.

Layout: - Top: Input slider for n (range 1 to 10, default 6) - Center: Tree visualization showing all recursive calls - Each tree node shows: function call (e.g., "fib(5)") and return value once computed - Left and right branches for the two recursive calls - Bottom: Statistics panel showing total calls, unique calls, and redundant calls

Interactive controls: - Slider to set n (1-10) - "Step" button: Reveals one function call at a time in depth-first order - "Auto Play" button: Animates the full tree building at adjustable speed - "Show Redundancy" toggle: Highlights duplicate calls in red (e.g., fib(2) appears multiple times) - "Reset" button

Visual elements: - Tree nodes as circles with function call text inside - Base case nodes (fib(0), fib(1)) shown in green - Redundant nodes highlighted in red when "Show Redundancy" is on - Edges connect parent to children - When a node's value is computed, it displays in gold text - Nodes appear with a gentle pop-in animation

Statistics panel: - Total function calls: [number] - Unique subproblems: [number] - Redundant calls: [number] ([percentage]%) - Bar chart comparing call counts for fib(1) through fib(n)

Color scheme: - Regular nodes: blue - Base case nodes: green - Redundant nodes: red - Return values: gold text - Edges: gray

Responsive: Tree auto-layouts to fit canvas width; may scroll horizontally for large n

Instructional Rationale: Tree recursion is the most visually dramatic demonstration of why naive recursion can be inefficient. By highlighting redundant calls, students immediately see that fib(2) is calculated many times -- motivating the eventual need for memoization. The statistics panel quantifies the waste, helping students develop intuition for algorithmic complexity. Step-by-step building of the tree supports the Analyze level by requiring students to predict branching behavior.

Combining It All: Higher-Order Functions Meet Recursion

Let's see how higher-order functions and recursion can work together. Here's a function that recursively applies a list of transformations to a value:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def apply_all(functions, value):
    """Recursively apply a list of functions to a value.

    Base case: no functions left, return the value.
    Recursive case: apply the first function, then recurse on the rest.
    """
    if len(functions) == 0:
        return value
    first_result = functions[0](value)
    return apply_all(functions[1:], first_result)

# Define some transformations
transformations = [
    lambda x: x * 2,      # Double it
    lambda x: x + 10,     # Add 10
    lambda x: x ** 2       # Square it
]

result = apply_all(transformations, 3)
print(result)  # 3 -> 6 -> 16 -> 256

This combines higher-order functions (passing functions in a list) with recursion (processing the list one function at a time). It's a beautiful example of how these two ideas complement each other.

Diagram: Recursion vs Iteration Side-by-Side

Recursion vs Iteration Side-by-Side Comparison

Type: microsim sim-id: recursion-vs-iteration
Library: p5.js
Status: Specified

Bloom Level: Evaluate (L5) Bloom Verb: compare, evaluate

Learning Objective: Students will be able to compare recursive and iterative implementations of the same algorithm side by side, tracking execution steps, memory usage, and output for each approach.

Layout: - Split screen: left half "Recursive", right half "Iterative" - Each side shows: code with line highlighting, variable state display, and step counter - Bottom: shared controls and comparison metrics

Algorithm selector: Dropdown to choose between: - Factorial - Sum of list - Countdown - Fibonacci (recursive only shows tree; iterative shows loop)

Left panel (Recursive): - Code display with line-by-line highlighting - Call stack visualization (mini version): frames stacking up - Current variable values for the active frame - Step counter

Right panel (Iterative): - Code display with line-by-line highlighting - Single set of variable values (no stack) - Loop counter display - Step counter

Bottom comparison metrics: - Steps taken: Recursive [N] vs Iterative [M] - Memory used: Recursive [call stack depth] vs Iterative [constant] - Output: [same value for both]

Interactive controls: - Algorithm dropdown selector - Input field for argument - "Step Both" button: Advance both sides one step simultaneously - "Run Both" button: Run to completion and show final metrics - "Reset" button

Color scheme: - Recursive panel: blue tones - Iterative panel: green tones - Active code line: yellow highlight - Metrics: neutral with colored bars for comparison

Responsive: Panels side-by-side on wide screens, stacked on narrow screens

Instructional Rationale: Direct side-by-side comparison is the most effective way to help students evaluate when to use recursion vs iteration. Seeing the same problem solved both ways -- with step counts and memory usage displayed -- gives students concrete evidence to reason about tradeoffs. This supports the Evaluate level by asking students to judge which approach is more appropriate for different scenarios.

Monty says: You've got this!

Monty You just conquered one of the toughest topics in all of computer science -- recursion! From lambda functions to map/filter/reduce, from function composition to recursive call stacks, you now have an incredibly powerful toolkit. These ideas will show up again and again as we tackle lists, sorting, and more advanced algorithms. Give yourself a pat on the back, coder!

Key Takeaways

  • Function documentation (docstrings) makes your code professional and self-explanatory. Always describe what a function does, its arguments, and its return value.
  • Helper functions break complex tasks into small, testable, reusable pieces.
  • The main function pattern (if __name__ == "__main__": main()) organizes your program and makes it importable.
  • Lambda functions let you define small, anonymous functions in a single line using lambda args: expression.
  • Higher-order functions take functions as arguments or return functions as results.
  • map() transforms every element in a list. filter() keeps elements that pass a test. reduce() combines all elements into a single value.
  • Function composition chains functions so the output of one becomes the input of the next.
  • Recursion is when a function calls itself. Every recursive function needs a base case (when to stop) and a recursive case (how to break the problem down).
  • The recursive call stack tracks all active function calls. Each call gets its own frame with its own local variables.
  • Stack overflow happens when recursion goes too deep -- usually from a missing or unreachable base case.
  • Recursion vs. iteration: recursion is elegant for naturally recursive problems; iteration is often faster and uses less memory.
  • Common recursive patterns include linear recursion, tree recursion, divide and conquer, and the accumulator pattern.
Check Your Understanding: What's wrong with this recursive function? 

1
2
3
def count_up(n):
    print(n)
    count_up(n + 1)
This function has no base case, so it will never stop calling itself. Each call increases n by 1, so there's no condition to halt the recursion. It will cause a stack overflow (Python's RecursionError). To fix it, add a base case, such as if n > 10: return.

Check Your Understanding: What does this code output? 

1
2
3
numbers = [1, 2, 3, 4, 5, 6]
result = list(filter(lambda x: x > 3, map(lambda x: x * 2, numbers)))
print(result)
First, map(lambda x: x * 2, numbers) doubles each number: [2, 4, 6, 8, 10, 12]. Then, filter(lambda x: x > 3, ...) keeps only values greater than 3: [4, 6, 8, 10, 12]. This is an example of composing map and filter together.

Check Your Understanding: Trace factorial(4) and list the call stack at its deepest point.

At its deepest point, the call stack contains (from bottom to top): factorial(4), factorial(3), factorial(2), factorial(1), factorial(0). That's 5 frames. The base case factorial(0) returns 1, then each frame above computes its result: 1*1 = 1, 2*1 = 2, 3*2 = 6, 4*6 = 24. The final answer is 24.