In the previous lesson we defined what an algorithm is and wrote our first one for RutaBus. Now we will step back to take in the whole landscape: algorithms can be classified along several dimensions —how they are structured, what they are for, whether their behavior is predictable, and whether they guarantee the exact solution—. Knowing these classifications matters because it gives you a mental map: when you face a new problem in RutaBus (or at work), you will know which "family" it belongs to and what kind of tool to look for. In this lesson you will also learn recursion in depth, a cross-cutting concept that will reappear in almost every module of the course.
Contents
- The classification dimensions
- By approach: iterative vs recursive
- Recursion in detail: base case and recursive case
- By purpose: searching, sorting, graphs, and more
- Deterministic vs non-deterministic
- Exact vs heuristic/approximate
- Preview: the design strategies of Module 3
The classification dimensions
The same algorithm can be classified along several independent criteria at once, just as a RutaBus stop can be classified at once by zone, by accessibility, and by the lines that serve it. The four dimensions we will cover are:
| Dimension | Question it answers | Typical values |
|---|---|---|
| Approach | How does it structure repetition? | Iterative, recursive |
| Purpose | What problem does it solve? | Searching, sorting, graphs, compression... |
| Determinism | Does it always behave the same on the same input? | Deterministic, non-deterministic |
| Exactness | Does it guarantee the optimal/correct solution? | Exact, heuristic/approximate |
For example, the nearest_stop algorithm from the previous lesson is iterative (it uses a loop), a search algorithm (it looks for a minimum), deterministic (the same input always produces the same output), and exact (it is guaranteed to find the truly nearest stop).
By approach: iterative vs recursive
The first dimension distinguishes how an algorithm repeats work.
- An iterative algorithm repeats steps using loops (
for,while), keeping its state in variables that get updated as it goes. - A recursive algorithm solves the problem by having a function call itself on a smaller version of the problem, until it reaches a case so simple it can be solved directly.
Let's look at the same RutaBus problem solved with both approaches: counting how many stops a line has, represented as a list of names.
line_l1 = ["Main Square", "Grand Avenue", "Central Hospital", "North Station"]
# ITERATIVE approach: a loop accumulates the result in a variable
def count_stops_iterative(stops):
counter = 0
for _ in stops: # for each stop...
counter += 1 # ...add 1 to the accumulator
return counter
# RECURSIVE approach: the function relies on itself
def count_stops_recursive(stops):
if not stops: # base case: empty list
return 0
return 1 + count_stops_recursive(stops[1:]) # recursive case
print(count_stops_iterative(line_l1)) # 4
print(count_stops_recursive(line_l1)) # 4The recursive version reads like this: "the number of stops in a list is 1 (the first one) plus the number of stops in the rest of the list; and an empty list has 0 stops". It is a definition of the problem in terms of itself, but with an ever smaller problem.
| Criterion | Iterative | Recursive |
|---|---|---|
| Repetition mechanism | Loops (for, while) |
Calls to the function itself |
| State | Variables updated on each pass | The parameters of each call |
| Readability | Better for simple linear problems | Better for problems with nested structure (trees, splits) |
| Memory usage | Generally constant | One call stack entry per pending call |
| Typical risk | Infinite loop from a badly written condition | RecursionError from a missing or unreachable base case |
Neither approach is "better" in the abstract: every recursive algorithm can be rewritten iteratively and vice versa. Recursion shines when the problem is naturally self-similar (exploring every combination of transfers, traversing hierarchical structures); iteration is usually preferable for simple linear traversals.
Recursion in detail: base case and recursive case
Every well-built recursive function has exactly two ingredients:
- Base case: the situation so simple it can be solved without recursion. It is the stopping condition. Without it (or if it is never reached), the function would call itself indefinitely.
- Recursive case: the function calls itself with an input that is strictly smaller or closer to the base case, and combines that partial result with some work of its own.
flowchart TD
A[Call with problem P] --> B{Is P the<br/>base case?}
B -- Yes --> C[/Return the direct solution/]
B -- No --> D[Reduce P to a smaller problem P']
D --> E[Recursive call with P']
E --> F[Combine the result of P'<br/>with the function's own work]
F --> G[/Return the result/]
Let's apply this to a real RutaBus problem: line L2 has its stops, and we want to know how many stops remain until the end of the route from the stop where the user currently is.
line_l2 = ["North Station", "Harbor Avenue", "Main Square",
"University", "South Terminal"]
def remaining_stops(line, current_stop):
"""Counts the stops that remain AFTER current_stop.
Base case: the current stop is the first of the remaining list
-> len - 1 stops remain... solved by counting recursively.
"""
# Base case: the current stop is the first in the list
if line[0] == current_stop:
return len(line) - 1
# Recursive case: drop the first stop and search in the rest
return remaining_stops(line[1:], current_stop)
print(remaining_stops(line_l2, "Main Square")) # 2 (University and South Terminal)Let's follow the execution trace to understand what happens under the hood:
remaining_stops(["North Station", "Harbor Avenue", "Main Square", "University", "South Terminal"], "Main Square")
→ "North Station" ≠ "Main Square" → recursive call with the list minus its first element
remaining_stops(["Harbor Avenue", "Main Square", "University", "South Terminal"], "Main Square")
→ "Harbor Avenue" ≠ "Main Square" → recursive call
remaining_stops(["Main Square", "University", "South Terminal"], "Main Square")
→ BASE CASE: returns len - 1 = 2
← 2
← 2
← 2Each pending call sits "on hold" on the call stack until the inner call returns its result. This explains the memory cost of recursion: with a line of 1,000 stops there could be up to 1,000 stacked calls (Python, by default, cuts off around 1,000 with a RecursionError).
Also notice a deliberate flaw in the example: if current_stop is not on the line, the list will eventually be empty and line[0] will raise an IndexError. An additional base case fixes it:
def remaining_stops_robust(line, current_stop):
if not line: # base case 2: stop not found
return None
if line[0] == current_stop: # base case 1: stop found
return len(line) - 1
return remaining_stops_robust(line[1:], current_stop)Golden rule: enumerate the base cases first (all of them), then write the recursive case, and check that every recursive call moves the input closer to some base case.
By purpose: searching, sorting, graphs, and more
The second dimension classifies algorithms by the kind of problem they solve. It is the most practical classification day to day, because real problems "look like" one of these families:
| Family | What it solves | RutaBus example | Where it is covered in depth |
|---|---|---|---|
| Searching | Locating an element (or the best one) in a collection | Finding the stop "Main Square" in the listing; binary search | Module 4 (04-01) |
| Sorting | Arranging elements according to a criterion | Sorting the upcoming buses by arrival time | Module 4 (04-02 to 04-04) |
| Graphs | Working with networks of nodes and connections | Computing the fastest route between two stops of the network | Module 4 (04-05, 04-06) |
| Compression | Reducing data size while preserving the information | Compressing the buses' GPS position history | (outside the scope of this course) |
| Cryptography | Protecting information | Encrypting the app users' credentials | (outside the scope of this course) |
| Numerical optimization | Minimizing/maximizing a function | Tuning service frequencies to minimize waits | Touched on in Modules 3 and 5 |
A small example of each of the two most frequent families, in a simple version (the efficient versions arrive in Module 4):
# SEARCHING (linear): at what position of the line is a given stop?
def find_stop(line, name):
for i, stop in enumerate(line):
if stop == name:
return i # found: return its index
return -1 # not found
# SORTING (delegated to Python): upcoming buses by arrival time
arrivals = [("L3", "10:42"), ("L1", "10:35"), ("L2", "10:39")]
by_time = sorted(arrivals, key=lambda bus: bus[1])
print(by_time) # [('L1', '10:35'), ('L2', '10:39'), ('L3', '10:42')]In find_stop, enumerate gives us both the index i and the value stop; we return the index as soon as there is a match (no need to keep looking). For sorting we use Python's sorted with a key function that states the criterion (the time, position 1 of each tuple) — in Module 4 we will open that "black box" and build our own sorting algorithms.
Deterministic vs non-deterministic
An algorithm is deterministic if, given the same input, it always executes exactly the same steps and always produces the same output. Everything we have written so far is deterministic, and that is the desirable default property: it makes software predictable and easy to test.
A non-deterministic algorithm (in practice, a randomized one) incorporates random decisions, so two runs on the same input may differ in their intermediate steps or even in their output. Far from being a defect, randomness is sometimes a valuable tool:
import random
def survey_stop(stops):
"""RutaBus wants to survey users at a randomly chosen stop
each day, so the sample isn't biased toward one area."""
return random.choice(stops)
# Two runs with the SAME input can produce different results:
print(survey_stop(["Main Square", "North Station", "South Terminal"]))| Aspect | Deterministic | Non-deterministic (randomized) |
|---|---|---|
| Same input → | Same output, always | Potentially different output (or path) |
| Testing / debugging | Simple and reproducible | Require fixing the seed (random.seed) |
| Typical uses | The vast majority of software | Sampling, simulation, avoiding pathological worst cases |
A note we will come back to: some famous algorithms use randomness to improve their typical behavior — for example, quicksort (Module 4) often picks its "pivot" at random. The output is still correct and the same; what varies is the path taken.
Exact vs heuristic/approximate
The last dimension answers: does the algorithm guarantee the best possible solution?
- An exact algorithm guarantees the correct or optimal solution.
nearest_stopis exact: the returned stop is truly the nearest one. - A heuristic or approximate algorithm gives up that guarantee in exchange for speed or simplicity: it produces a reasonably good solution most of the time, but it can be wrong or land far from the optimum.
Why give up exactness? Because there are problems where finding the exact optimum is unaffordably expensive. A classic example adapted to RutaBus: a supervisor must visit 20 stops in a single tour, minimizing total distance (the famous "traveling salesman problem"). The number of possible tours is astronomical, so a reasonable heuristic is: "from each stop, always go to the nearest unvisited one".
def supervisor_route(stops, start):
"""'Nearest neighbor' heuristic: a short tour, not necessarily optimal."""
pending = [p for p in stops if p["name"] != start["name"]]
route = [start]
current = start
while pending:
# Pick the pending stop closest to the current one
next_stop = min(
pending,
key=lambda p: distance(current["x"], current["y"], p["x"], p["y"])
)
route.append(next_stop)
pending.remove(next_stop)
current = next_stop
return routeThis heuristic produces good tours in practice, but it can be proven that it sometimes returns tours clearly worse than the optimum. That is the deal: speed in exchange for guarantees.
| Aspect | Exact | Heuristic/approximate |
|---|---|---|
| Guarantee on the solution | Optimal/correct, always | "Good", with no guarantee (or with an error bound) |
| Computational cost | Can be prohibitive on hard problems | Usually low |
| When to choose it | Whenever the cost is affordable | Intractable problems or strict time limits |
A vocabulary nuance: approximate usually refers to an algorithm offering a mathematical guarantee of closeness to the optimum (e.g., "at most twice the optimum"), while heuristic refers to one offering none — just good empirical behavior.
Preview: the design strategies of Module 3
Beyond the dimensions above, algorithms are often grouped by the design strategy used to build them. We only name them here — each has its own lesson in Module 3:
- Divide and conquer (03-01): split the problem into smaller subproblems, solve them, and combine their solutions.
- Greedy (03-02): build the solution by making the locally best decision at each step — the supervisor heuristic we just saw is greedy in spirit.
- Dynamic programming (03-03): solve recurring subproblems while storing their results so they are never recomputed.
- Backtracking (03-04): systematically explore every option, backing up whenever a path leads to no solution.
Common Mistakes and Tips
- Forgetting the base case (or one of them) in a recursive function. The symptom in Python is
RecursionError: maximum recursion depth exceeded. Tip: write the base cases before the recursive case, and ask yourself "which inputs should NOT trigger another call?". - A recursive call that doesn't shrink the problem.
remaining_stops(line, current_stop)calling itself with the same list never terminates. Verify that each recursive call passes an input strictly closer to a base case. - Using recursion for long linear traversals in Python. With lists of thousands of elements you will exhaust the stack. For simple traversals, prefer iteration; save recursion for problems with a branching structure.
- Believing that "non-deterministic" means "incorrect". A well-designed randomized algorithm is just as legitimate as a deterministic one; it merely demands extra discipline in testing (fix
random.seed(42)to reproduce runs). - Using a heuristic when the problem has a cheap exact solution. Before settling for "approximate" answers, check whether an efficient exact algorithm exists for your problem (it often does, and it's in Module 4).
- Classifying the problem too late. Professional tip: before coding, ask "is this searching, sorting, graphs...?". Identifying the family points you straight to known solutions instead of reinventing them.
Exercises
Exercise 1
Classify the supervisor_route function from this lesson along the four dimensions (approach, purpose, determinism, exactness) and justify each answer in one sentence.
Exercise 2
Write a recursive function has_stop_recursive(line, name) that returns True if the stop name is in the list line and False otherwise. Explicitly identify in comments the base case (or base cases) and the recursive case. Then write the iterative version and compare: which one seems clearer to you for this problem?
Exercise 3
The following recursive function is meant to add up the waiting minutes in a list, but it has two bugs. Find and fix them:
Solutions
Solution 1:
- Approach: iterative — it repeats via a
whileloop, without calling itself. - Purpose: optimization (it looks for a short tour), relying on minimum-finding search operations.
- Determinism: deterministic — with the same stops and the same start it always produces the same tour (Python's
minresolves ties the same way every time: the first one wins). - Exactness: heuristic — it does not guarantee the minimum-distance tour, only a reasonably short one.
Solution 2:
# Recursive version
def has_stop_recursive(line, name):
if not line: # BASE CASE 1: empty list -> not there
return False
if line[0] == name: # BASE CASE 2: the first one matches -> it's there
return True
# RECURSIVE CASE: search the rest of the list (a smaller problem)
return has_stop_recursive(line[1:], name)
# Iterative version
def has_stop_iterative(line, name):
for stop in line:
if stop == name:
return True
return FalseFor a linear traversal like this one, the iterative version is usually considered clearer and it also uses no stack. The recursive one is a good exercise, but in production (and in Python) the iterative one is the natural choice. Note that two base cases are needed: one for success and one for failure.
Solution 3:
Bugs:
- The recursive call doesn't shrink the problem:
total_wait(waits)is called with the same list, causing infinite recursion. It must betotal_wait(waits[1:]). - The empty-list base case is missing: with
waits = [], the conditionlen(waits) == 1is false andwaits[0]raises anIndexError. The cleanest fix is to make the empty list the base case (which also lets the recursive case coverlen == 1).
def total_wait(waits):
if not waits: # base case: an empty list sums to 0
return 0
return waits[0] + total_wait(waits[1:]) # recursive case: shrink the list
print(total_wait([5, 3, 8])) # 16
print(total_wait([])) # 0Conclusion
In this lesson we built a map of algorithm types along four independent dimensions: by approach (iterative versus recursive, with recursion explained in depth through base case and recursive case), by purpose (searching, sorting, graphs, compression...), by determinism (predictable versus randomized), and by exactness (exact versus heuristic/approximate). We also caught a glimpse of the four major design strategies we will develop in Module 3. With this map we now know which families of algorithms exist; the natural next question is how to compare two algorithms from the same family that solve the same problem. For that we need a common, machine-independent language: asymptotic notation, the star of the next lesson.