Recursion: Principles and Algorithms

From connected data to self-repeating problems

In Introduction to Data Structures, you saw that the way we organize information changes the code we write. In Graphs: Concepts and Operations, you worked with nonlinear relationships and traversal ideas.

Now we add a new problem-solving tool: recursion.

Recursion is when a function solves a problem by solving smaller versions of the same problem. It shows up in graph traversal, file folders, game decisions, puzzles, and many interview-style algorithms.

Think of a true-crime investigation board: to understand one suspect, you may need to investigate their contacts; for each contact, you repeat the same process on a smaller part of the case.

Every safe recursion needs three parts

A recursive function is like making a promise:

1. Base case — When do we stop?
2. Progress — How does each call move closer to stopping?
3. Recursive call — Where do we solve a smaller version of the same problem?

Without a base case, recursion can keep calling itself until Python raises an error. Without progress, the base case may never be reached.

A useful mental model:

solve(big problem)
  -> solve(smaller problem)
      -> solve(even smaller problem)
          -> base case
      <- return result
  <- combine result

A recursive function is supposed to count down from n to 0.

Which condition is the most direct base case?

A classic first recursive algorithm

The factorial of a number multiplies that number by every positive integer below it.

5! = 5 × 4 × 3 × 2 × 1 = 120

Recursive idea:

factorial(n) = n × factorial(n - 1)

But we still need the base case:

factorial(0) = 1

Why 1? Because multiplying by 1 does not change the result, so it cleanly ends the chain.

```python
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print("factorial(5) =", factorial(5))
print("factorial(0) =", factorial(0))
```

Complete the missing base-case return value:

factorial(0) should return ____.

Recursion is not magic

Many recursive solutions can also be written with loops.

The difference is usually about how the work is expressed:

• Iteration repeats using a loop.
• Recursion repeats using function calls.

For a simple countdown, either version works. Recursion becomes especially elegant when the problem naturally contains smaller versions of itself.

```python
def countdown_recursive(n):
    if n == 0:
        return ["Tipoff!"]
    return [str(n)] + countdown_recursive(n - 1)


def countdown_iterative(n):
    result = []
    while n > 0:
        result.append(str(n))
        n -= 1
    result.append("Tipoff!")
    return result

print("Recursive:", " -> ".join(countdown_recursive(3)))
print("Iterative:", " -> ".join(countdown_iterative(3)))
```

True or false:

A recursive solution is always faster and better than an iterative solution.

Some recursion grows quickly

Factorial makes one smaller call each time:

factorial(5) -> factorial(4) -> factorial(3) -> ...

But some algorithms make multiple recursive calls.

The Fibonacci sequence is a famous example:

fib(n) = fib(n - 1) + fib(n - 2)

That branching can repeat the same work many times. Later, when we study hashmaps, you will see how fast lookup can help avoid repeated calculations.

```python
calls = 0

def fib(n):
    global calls
    calls += 1

    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

for n in [4, 6, 8]:
    calls = 0
    value = fib(n)
    print(f"fib({n}) = {value}, function calls = {calls}")
```

Applying recursion to a familiar structure

In Graphs: Concepts and Operations, you learned that adjacency lists describe who connects to whom.

Recursion gives us a natural way to explore those connections: visit a node, then recursively visit its neighbors.

Here, we search for whether a path exists from one person to another in a small investigation network.

```python
graph = {
    "Detective": ["Witness", "Analyst"],
    "Witness": ["Neighbor"],
    "Analyst": ["Phone Records", "Security Footage"],
    "Neighbor": [],
    "Phone Records": [],
    "Security Footage": ["Suspect"] ,
    "Suspect": []
}


def has_path(graph, current, target, visited=None):
    if visited is None:
        visited = set()

    if current == target:
        return True

    if current in visited:
        return False

    visited.add(current)

    for neighbor in graph[current]:
        if has_path(graph, neighbor, target, visited):
            return True

    return False

print("Path to Suspect?", has_path(graph, "Detective", "Suspect"))
print("Path to Coach?", has_path(graph, "Detective", "Coach" if "Coach" in graph else "Coach"))
```

Before writing recursive code, ask:

• What is the smaller version of this problem?
• What is the base case?
• Does every call move closer to that base case?
• What should each call return?
• Do I combine returned values, or just pass success/failure upward?

Recursion is a lens: it helps you see repeated structure inside a problem.

You have now added a major algorithmic pattern to your toolkit. Next, we move to Hashmaps: Efficient Data Retrieval, where the focus shifts from repeated structure to fast lookup.