Recursion - Problems Within Problems

Card 14 of 15

What Is Recursion?

"An approach to solving problems that involves breaking down a problem into smaller ones until we find a simple problem that we can solve - then cascade the solution back up."

The Recursive Mindset

Counting: factorial(5) = 5 × 4 × 3 × 2 × 1

factorial(5) = 5 × factorial(4)

factorial(4) = 4 × factorial(3)

factorial(3) = 3 × factorial(2)

factorial(2) = 2 × factorial(1)

factorial(1) = 1 BASE CASE!

↓ CASCADE BACK UP ↓

factorial(1) = 1

factorial(2) = 2 × 1 = 2

factorial(3) = 3 × 2 = 6

factorial(4) = 4 × 6 = 24

factorial(5) = 5 × 24 = 120

Three Characteristics of Recursion

1. Base Case

A simple problem that can be solved directly. Recursion must stop somewhere!

if n == 1: return 1

2. Move Toward Base

Each recursive call must get closer to the base case

factorial(n-1)

3. Call Itself

Function must call itself with a smaller problem

return n * factorial(n-1)

Critical: Without a base case, recursion never stops - infinite loop!

Recursive Code Example

def factorial(n):
    # 1. BASE CASE - stop condition
    if n == 1:
        return 1

    # 2. RECURSIVE CASE - call itself
    # 3. MOVE TOWARD BASE - n-1 is smaller than n
    return n * factorial(n - 1)

# Call it
result = factorial(5)  # 120

Interactive Recursion Visualizer

Calculate factorial of:

Enter a number and click visualize

Result will appear here

When to Use Recursion

Naturally recursive problems: Tree traversal, file systems
Divide and conquer: Breaking big problems into smaller ones
Mathematical sequences: Factorials, Fibonacci
When the problem can be defined in terms of itself

"Recursion is powerful but can be tricky. The key insight: solve the smallest version first (base case), then define bigger versions in terms of smaller ones."

Mental Model: Recursion is like Russian nesting dolls. You open one doll to find a smaller one inside. Keep opening until you find the smallest doll (base case), then close them all back up (cascade the solution).

                [############################..] 14/15
            