Mastering Recursion

From structures to self-similar thinking

In Introduction to Data Structures, you practiced choosing tools like lists, stacks, queues, sets, and maps based on the operations you need.

Today we add a new mental tool: recursion — solving a problem by reducing it into smaller versions of the same problem.

Recursion matters because it shows up in many interview-style problems:

• nested structures
• tree-like decisions
• combinations and permutations
• search paths
• problems where each step looks like the previous step

For this crash course, your goal is not to make everything recursive. Your goal is to recognize when recursion is natural, write it safely, and trace it without panic.

A recursive function has two jobs

Every safe recursive function needs:

1. Base case — the smallest case we can answer immediately.
2. Recursive case — the rule that makes progress toward the base case.

Think of it like this:

solve(problem):
    if problem is tiny enough:
        return direct answer
    return solve(smaller problem)

The danger is not recursion itself. The danger is calling the function again without getting closer to stopping.

```python
def countdown(n):
    print(f'enter countdown({n})')

    if n == 0:
        print('base case!')
        return

    countdown(n - 1)
    print(f'returning from countdown({n})')

countdown(3)
```

A recursive function keeps calling itself, but its input never gets closer to a stopping condition.

What is the most likely result?

Recursion uses the call stack

When a function calls itself, Python pauses the current call and starts a new one.

Each paused call keeps its own local variables.

countdown(3)
  waits for countdown(2)
    waits for countdown(1)
      waits for countdown(0)
        base case returns
      countdown(1) resumes
    countdown(2) resumes
  countdown(3) resumes

This is why recursion often feels like going down until the base case, then coming back up as calls return.

The stack idea connects directly to the stack structure you saw in the previous lesson, but here Python manages that stack for function calls.

Complete the sentence:

Every recursive function needs at least one reachable ____ that stops the chain of recursive calls.

Recursion over a list

A list sum can be described recursively:

sum from index i = nums[i] + sum from index i + 1

The smaller problem is: sum the rest of the list.

The base case is when i reaches the end of the list. At that point, there is nothing left to add, so the answer is 0.

This is not always the fastest or cleanest way to sum a list in Python, but it is excellent practice for seeing recursive structure.

```python
def recursive_sum(nums, i=0):
    if i == len(nums):
        return 0

    return nums[i] + recursive_sum(nums, i + 1)

print(recursive_sum([4, 1, 7]))
print(recursive_sum([]))
```

True or false?

A recursive solution is usually better than an iterative one simply because it uses recursion.

Some calls split into choices

Not all recursion is one straight chain. Sometimes each call creates multiple smaller calls.

Example task: print all binary strings of length n.

At each position, choose either:

• 0
• 1

This creates a branching tree of decisions. The base case is when the string has length n.

This pattern is useful for practicing recursion before later lessons introduce more advanced strategies.

```python
def binary_strings(n, prefix=''):
    if len(prefix) == n:
        print(prefix)
        return

    binary_strings(n, prefix + '0')
    binary_strings(n, prefix + '1')

binary_strings(3)
```

A quick recursion checklist

Before writing code, answer these questions:

1. What is the function supposed to return or do?
2. What is the smallest input I can solve immediately?
3. How do I make the input smaller?
4. How do I combine the smaller answer into the current answer?
5. Can I trace a tiny example by hand?

For beginner Python learners, step 5 is huge. If you can trace n = 2 or a list of length 2, you can usually debug the full version.

In this 30-day crash course, recursion will become a foundation for later problem-solving patterns without needing to memorize every possible problem type.

Your two-day review loop

Because this course emphasizes revisiting problems every 2 days, do not treat recursion as a one-time topic.

Practice these small drills:

• Day 1: write countdown, factorial, or recursive_sum
• Day 3: rewrite from memory and trace each call
• Day 5: solve one branching recursion problem like binary strings
• Day 7: return to the first problem and explain the base case out loud

When you review, focus on the same three labels every time:

base case
recursive case
progress toward stopping

Next, we will move into sorting algorithms, where careful tracing and step-by-step thinking continue to matter.