🪆 Recursion

The Russian Dolls Analogy

You have a Russian nesting doll (Matryoshka). You want to find the smallest doll.

What you do:

1. Open the doll
2. Is there a doll inside?
   • YES → Repeat from step 1 with the inner doll
   • NO → This is the smallest! Stop.

Each doll contains a smaller version of the same problem. You keep going until you reach the one that can't be opened.

That's recursion!

A function that calls itself with a smaller version of the problem, until it reaches a case that doesn't need further breaking down.

Why Recursion Exists

Some problems are naturally recursive:

• File system: A folder contains files AND folders (which contain more files and folders)
• Family tree: A person has parents, who have parents, who have parents...
• HTML: Elements contain other elements, which contain more elements
• Math: Factorial: 5! = 5 × 4! = 5 × 4 × 3! = 5 × 4 × 3 × 2! = 5 × 4 × 3 × 2 × 1

These problems have a self-similar structure - they contain smaller versions of themselves.

The Two Essential Parts

Every recursive function needs:

1. Base Case: When to STOP

Without this, the function can keep calling itself and may not finish.

if (problem is simple enough):
    return the answer directly  ← BASE CASE

2. Recursive Case: Call yourself with a SMALLER problem

else:
    return combine(this step + solve(smaller problem))  ← RECURSIVE CASE

In practice, you usually need both.

A Simple Example: Countdown

Problem: Count down from 5 to 1

Thinking recursively:

• To count from 5: Say "5", then count from 4
• To count from 4: Say "4", then count from 3
• ...
• To count from 1: Say "1", then STOP (base case!)

countdown(5):
  print 5
  countdown(4)
    print 4
    countdown(3)
      print 3
      countdown(2)
        print 2
        countdown(1)
          print 1
          STOP (base case: n = 1)

How It Actually Works

When a function calls itself, each call waits for the inner call to finish:

factorial(5)
├── return 5 × factorial(4)  ← waiting...
    ├── return 4 × factorial(3)  ← waiting...
        ├── return 3 × factorial(2)  ← waiting...
            ├── return 2 × factorial(1)  ← waiting...
                └── return 1  ← BASE CASE! Returns 1
            └── 2 × 1 = 2  ← Now this can finish
        └── 3 × 2 = 6  ← Now this can finish
    └── 4 × 6 = 24  ← Now this can finish
└── 5 × 24 = 120  ← Final answer!

It's like a stack of plates - last one added is first one resolved.

Real-World Examples

1. File System Search

Find all files in a directory (including subdirectories):

searchDirectory(folder):
  for each item in folder:
    if item is a file:
      add to results
    if item is a folder:
      searchDirectory(item)  ← Recursive call!

2. Family Tree Traversal

Find all ancestors:

getAncestors(person):
  parents = person.parents
  for each parent:
    add parent to list
    getAncestors(parent)  ← Recursive call!

3. DOM Traversal

Find all children of an HTML element:

getAllChildren(element):
  for each child of element:
    add child to list
    getAllChildren(child)  ← Recursive call!

Recursion vs Loops

Anything recursion can do, loops can do (and vice versa).

Use recursion when:

• The problem is naturally recursive (trees, nested structures)
• The recursive solution is much cleaner than loops

Use loops when:

• You're processing a simple list
• Performance is critical
• Deep nesting could cause stack overflow

Common Mistakes

Mistake 1: No Base Case (Infinite Recursion)

// ❌ Won't stop (no base case)
countdown(n):
  print(n)
  countdown(n - 1)  // What if n reaches 0? Keeps going!

// ✓ Correct - has a stopping point
countdown(n):
  if n <= 0:
    return  // BASE CASE!
  print(n)
  countdown(n - 1)

Mistake 2: Not Moving Toward Base Case

// ❌ n doesn't get smaller
factorial(n):
  if n == 1: return 1
  return n * factorial(n)  // Should be n-1!

// ✓ Correct - n decreases each call
factorial(n):
  if n == 1: return 1
  return n * factorial(n - 1)

Mistake 3: Too Deep Recursion (Stack Overflow)

// ❌ Might overflow for large numbers
processMillionItems(list):
  if list.empty: return
  process(list[0])
  processMillionItems(list.slice(1))  // 1 million calls!

// ✓ Better - use a loop for large linear data
for item in list:
  process(item)

Understanding the Call Stack

Each function call gets added to a "stack" in memory:

main()
  ↓ calls
factorial(5)
  ↓ calls
factorial(4)
  ↓ calls
factorial(3)
  ↓ calls
factorial(2)
  ↓ calls
factorial(1)  ← Stack is 6 calls deep!

When factorial(1) returns, it "pops" off the stack. Then factorial(2) can finish, and so on.

Stack Overflow: If the stack gets too deep (usually thousands of calls), you run out of memory. This is called a "stack overflow."

FAQ

Q: When should I use recursion instead of loops?

Use recursion when the problem is naturally recursive (tree structures, nested data). Use loops for simple iteration.

Q: What is stack overflow?

When recursion goes too deep, you run out of memory. Each call adds to the stack. Too many calls = overflow.

Q: Can all recursive functions be converted to loops?

Yes! Sometimes it requires a manual stack. But just because you CAN doesn't mean you should - recursion is often cleaner for certain problems.

Q: What is tail recursion?

When the recursive call is the LAST thing the function does. Some languages optimize this to avoid stack growth.

Q: How do I debug recursive functions?

Add print statements at the start of each call showing the parameters. Watch how the problem gets smaller.

Q: How does recursion compare with loops?

It can be a bit slower due to function call overhead, but for many real programs the difference isn’t the main factor. Readability and correctness often matter more.

Summary

Recursion is a function calling itself with a smaller problem until it reaches a base case. It's powerful for naturally recursive problems like trees and nested structures.

Key Takeaways:

• Recursive function = calls itself
• Needs a base case (when to stop)
• Needs to move toward the base case
• Works like a stack - last in, first out
• Great for trees, nested structures, divide-and-conquer
• Can cause stack overflow if too deep
• Loops are often simpler for linear problems

Think of recursion as breaking a problem into smaller, identical problems until they become trivial to solve!