Recursion

🔄 Recursion: The Magic Mirror of Code

The Story of the Nesting Dolls 🪆

Imagine you have a Russian nesting doll. You open it, and there’s a smaller doll inside. You open that one, and there’s an even smaller doll. You keep opening until you find the tiniest doll that doesn’t open anymore.

That’s recursion! A function that calls itself, getting smaller each time, until it reaches the tiniest case that stops the chain.

🎯 What is a Recursive Function?

A recursive function is a function that calls itself.

Think of it like looking into a mirror while holding another mirror. You see yourself, holding a mirror, showing yourself, holding a mirror… it goes on and on!

But in coding, we need a way to STOP. Otherwise, we’d be trapped forever!

Simple Example: Counting Down

def countdown(n):
    if n == 0:
        print("Blast off! 🚀")
    else:
        print(n)
        countdown(n - 1)

countdown(3)

Output:

3
2
1
Blast off! 🚀

What happened?

• countdown(3) prints 3, then calls countdown(2)
• countdown(2) prints 2, then calls countdown(1)
• countdown(1) prints 1, then calls countdown(0)
• countdown(0) prints “Blast off!” and STOPS

🛑 Base Case: The Stopping Point

Every recursive function needs a base case. This is the condition that says “STOP! Don’t call yourself again!”

Without a base case, your function would call itself forever (until your computer runs out of memory).

The Two Essential Parts

graph TD
    A["Function Called"] --> B{Check Base Case}
    B -->|Yes| C["Return/Stop"]
    B -->|No| D["Do Something"]
    D --> E["Call Self with Smaller Problem"]
    E --> A

Think of it like eating pizza:

• 🍕 Base Case: “No slices left? Stop eating!”
• 🔄 Recursive Case: “Eat one slice, then handle the rest”

Example: Finding Factorial

Factorial means multiplying a number by all smaller numbers down to 1.

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

def factorial(n):
    # Base case: stop here!
    if n == 1:
        return 1
    # Recursive case: keep going
    else:
        return n * factorial(n - 1)

print(factorial(5))  # Output: 120

How it works:

factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1
= 120

🔄 Recursive Case: The Repeating Step

The recursive case is where the magic happens. It’s the part where the function calls itself with a smaller or simpler version of the problem.

Key Rule

Each recursive call must move CLOSER to the base case!

Like climbing down stairs:

• Start at step 10
• Go to step 9, then 8, then 7…
• Eventually reach step 0 (ground floor = base case)

Example: Sum of Numbers

Add all numbers from 1 to n:

def sum_to(n):
    if n == 1:        # Base case
        return 1
    else:             # Recursive case
        return n + sum_to(n - 1)

print(sum_to(5))  # Output: 15

Breakdown:

sum_to(5) = 5 + sum_to(4)
          = 5 + 4 + sum_to(3)
          = 5 + 4 + 3 + sum_to(2)
          = 5 + 4 + 3 + 2 + sum_to(1)
          = 5 + 4 + 3 + 2 + 1
          = 15

⚔️ Recursion vs Iteration: The Battle

Iteration uses loops (for, while). Recursion uses function calls.

Both can solve the same problems, but they think differently!

Same Problem, Two Ways

Counting down with ITERATION (loop):

def countdown_loop(n):
    while n > 0:
        print(n)
        n = n - 1
    print("Blast off! 🚀")

Counting down with RECURSION:

def countdown_recursive(n):
    if n == 0:
        print("Blast off! 🚀")
    else:
        print(n)
        countdown_recursive(n - 1)

When to Use Which?

graph TD
    A["Problem Type?"] --> B{Naturally Nested?}
    B -->|Yes| C["Use Recursion ✨"]
    B -->|No| D{Simple Repeat?}
    D -->|Yes| E["Use Iteration 🔁"]
    D -->|No| F["Either Works!"]

Real Example: Calculate Power

n raised to power p (like 2³ = 8)

Iteration approach:

def power_loop(n, p):
    result = 1
    for i in range(p):
        result = result * n
    return result

Recursion approach:

def power_recursive(n, p):
    if p == 0:
        return 1
    else:
        return n * power_recursive(n, p - 1)

🎨 Beautiful Recursion: Fibonacci

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13…

Each number is the sum of the two before it!

def fibonacci(n):
    if n <= 1:        # Base cases
        return n
    else:             # Recursive case
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(6))  # Output: 8

The sequence builds like a tree:

fib(4)
├── fib(3)
│   ├── fib(2)
│   │   ├── fib(1) = 1
│   │   └── fib(0) = 0
│   └── fib(1) = 1
└── fib(2)
    ├── fib(1) = 1
    └── fib(0) = 0

💡 Quick Tips for Writing Recursion

1. Always define your base case FIRST

   • What’s the simplest version of this problem?
   • When should I stop?

2. Make progress toward the base case

   • Each call must get smaller/simpler
   • Don’t call with the same value!

3. Trust the magic

   • Assume the recursive call works
   • Focus on one step at a time

4. Test with small numbers first

   • Start with n=1, n=2, n=3
   • Draw out the calls on paper

🏆 You’ve Learned

✅ Recursive Functions - Functions that call themselves

✅ Base Case - The condition that stops recursion

✅ Recursive Case - The step that calls itself with a smaller problem

✅ Recursion vs Iteration - Two ways to repeat, each with strengths

Remember the nesting doll! Open, find smaller, repeat… until you find the tiny one that doesn’t open. That’s recursion in a nutshell! 🪆