Recursive Problem Solving

Hello! Welcome back.

In our last lesson, we introduced the fundamental concept of recursion. We learned that every recursive function has two key parts: a base case that stops the process and a recursive step where the function calls itself with a simpler input. You also saw how the call stack manages this process behind the scenes.

Today, we move from understanding what recursion is to learning how to use it effectively. Our goal is to design recursive solutions for problems that can be broken down into smaller, self-similar subproblems. We will explore a systematic approach to turn a complex problem into an elegant recursive function, a crucial skill for competitive programming.

The "Divide and Conquer" Mindset

At its heart, designing a recursive solution is about "divide and conquer." You take a large problem and break it down into smaller, more manageable versions of the exact same problem. You keep breaking it down until you reach a "base case" that is so simple you can solve it instantly.

Recursive Present Delivery System — This diagram illustrates the "divide and conquer" strategy. A head elf doesn't deliver all the presents; they divide the task among sub-elves, who in turn divide their tasks further. This continues until the task is simple enough for one elf to handle (the base case: delivering to a single house).

This process of breaking things down is the key to recursive design. Let's learn a formal framework for doing this.

A 5-Step Framework for Recursive Design

Thinking recursively can be tricky at first. Having a structured process helps immensely. The video below outlines a five-step method that you can apply to almost any recursive problem.

5 Simple Steps for Solving Any Recursive Problem

Watch this segment from the video '5 Simple Steps for Solving Any Recursive Problem' by Reducible. It will introduce the five-step framework and apply it to the familiar problem of summing numbers, which we touched on last lesson.

Watch from the beginning to 06:17. Pay close attention to the five steps as they are presented and applied.

As the video explained, the five steps to designing a recursive solution are:

Find the base case: Ask yourself, "What is the simplest possible input for this problem?" This is the input you can solve without any further recursion.
Play with examples: Work through a few examples by hand to understand the problem's behavior. Visualizing the problem helps.
Relate larger cases to smaller cases: This is the most crucial step. Find the recursive relationship. Ask, "If I had the solution for a simpler version of the problem (e.g., for n-1), how could I find the solution for the current problem (e.g., for n)?"
Generalize the pattern: Express the relationship from the previous step as a general formula or rule. For example, sum(n) = n + sum(n-1).
Write the code: Combine your base case (from Step 1) and your recursive rule (from Step 4) into a function.

Applying the Framework: Unique Paths in a Grid

Now, let's use this framework on a classic competitive programming problem that isn't as immediately obvious as sum(n).

Problem: Given an N x M grid, find the number of unique paths from the top-left corner (0, 0) to the bottom-right corner (N-1, M-1), assuming you can only move right or down.

This might seem complex to solve with loops, but it's a perfect candidate for recursion. Let's see how our 5-step framework simplifies it.

5 Simple Steps for Solving Any Recursive Problem

Let's continue with the Reducible video, where the presenter applies the exact same five steps to solve the unique paths problem.

Watch from 06:03 to 11:17. Observe how the complex problem is broken down into a simple recursive formula.

Let's quickly review the application of the five steps to the grid problem:

Base Case: What's the simplest grid? Any grid where N=1 or M=1. In a 1xM or Nx1 grid, there's only one possible path. So, if n == 1 or m == 1, we return 1.
Examples: Visualizing a 2x2 grid (2 paths) or a 3x2 grid (3 paths) helps build intuition.
Relate Cases: To get to the cell (n, m), you must have come from either the cell above, (n-1, m), or the cell to the left, (n, m-1). Therefore, the total number of paths to (n, m) is the sum of the paths to those two cells.
Generalize the Pattern: This gives us our recursive formula:
$paths (n, m) = paths (n - 1, m) + paths (n, m - 1)$

Write Code: Combining the base case and the recursive rule gives us this elegant solution:

def unique_paths(n, m):
    # Base Case: If we are in the first row or first column, there's only one way.
    if n == 1 or m == 1:
        return 1
    # Recursive Step: Sum of paths from the cell above and the cell to the left.
    else:
        return unique_paths(n - 1, m) + unique_paths(n, m - 1)

# Example for a 3x3 grid
print(unique_paths(3, 3)) # Output: 6

Notice how a complex-sounding problem becomes a few simple lines of code once we find the recursive structure.

Recognizing Self-Similar Structures

The "divide and conquer" strategy works beautifully when a problem's structure is inherently recursive. Let's look at two more classic examples.

1. Traversing a Nested List

Some data structures are recursive by nature. A nested list is a list that contains other lists. The problem of processing items in a list can be applied to the main list and then recursively to any sublists.

Recursion in Python: An Introduction

The article 'Recursion in Python: An Introduction' from Real Python has an excellent section on this. Read about the problem of counting 'leaf' items in a nested list and see how naturally recursion solves it.

Read the section titled 'Traverse a Nested List'. Start from the problem description with the names list and go through to the implementation of count_leaf_items(). Focus on how the function calls itself whenever it encounters a sublist.

The recursive insight here is:

Base Case: If an item is not a list, it's a "leaf." Count it as 1.
Recursive Step: If an item is a list, then the number of leaves it contains is found by running the same counting function on that sublist.

2. The Towers of Hanoi

The Towers of Hanoi is a famous puzzle. Its solution is notoriously difficult to formulate with loops, but stunningly simple with recursion. The problem is to move a stack of disks from one rod to another, following two rules:

Only one disk can be moved at a time.
A larger disk can never be placed on top of a smaller disk.

6. Recursion and Dictionaries

Watch this segment from the MIT OpenCourseWare lecture on recursion. The professor explains the puzzle and demonstrates the beautiful recursive solution.

Watch from 20:08 to 24:20. Focus on the core recursive insight: to move a stack of N disks, you first move a stack of N-1 disks out of the way.

The recursive solution to move N disks from a source rod to a destination rod is:

Base Case: If you only have 1 disk, just move it directly from source to destination.
Recursive Step (for N > 1 disks):
- Move N-1 disks from the source rod to the spare rod.
- Move the Nth (largest) disk from the source rod to the destination rod.
- Move the N-1 disks from the spare rod to the destination rod.

This is a prime example of finding a self-similar subproblem that makes the overall solution trivial to express.

Test your understanding!

A palindrome is a word that reads the same forwards and backward, like "racecar" or "level".

Using the 5-step design framework, design a recursive function is_palindrome(word) that returns True if a string is a palindrome and False otherwise.

Show answer

Let's apply the 5-step framework:

Base Case: What's the simplest word? An empty string ("") or a string with one character ("a") is always a palindrome. So, if len(word) <= 1, return True.
Play with examples:
- "racecar" -> r == r. Now check "aceca".
- "aceca" -> a == a. Now check "cec".
- "cec" -> c == c. Now check "e".
- "e" is the base case, returns True. So the whole word is a palindrome.
Relate Cases: A word is a palindrome if its first and last characters are the same, and the substring between them is also a palindrome.
Generalize the Pattern: is_palindrome(word) = (word[0] == word[-1]) and is_palindrome(word[1:-1]).

Write Code:

def is_palindrome(word):
    # Base Case
    if len(word) <= 1:
        return True
    # Recursive Step
    else:
        # Check if the outer characters match and the inner part is a palindrome
        return word[0] == word[-1] and is_palindrome(word[1:-1])

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

Conclusion

Today we transformed our theoretical knowledge of recursion into a practical design skill. You learned a systematic process to break down problems and translate them into recursive code, a technique that is fundamental in algorithm design and competitive programming.

Key Takeaways:

Recursive design is a form of "divide and conquer": break a problem into smaller, self-similar subproblems.
A 5-step framework can guide your thinking: find the base case, experiment, find the recursive relation, generalize it, and then code it.
Recursion is particularly powerful for problems with an inherently recursive structure, like traversing nested data (lists, trees) or solving puzzles like the Towers of Hanoi.
The elegance of recursion often lies in expressing a complex process in just a few lines of code once the self-similar pattern is found.

Up Next:
You've now seen what recursion is and how to design with it. In the next lesson, we will dive deeper into the mechanics. We will trace the call stack for a simple recursive function to build a precise mental model of how the computer executes and keeps track of all the nested calls. This will be crucial for debugging and analyzing the performance of your recursive algorithms.

Recommended resources