Recursion is when a function calls itself. Think of it as Russian nesting dolls - each doll contains a smaller version of itself.
Open a Russian doll, find another doll inside. Open that doll, find another smaller one. Keep going until you reach the smallest doll. Recursion works the same way - a function calls itself with smaller inputs until it reaches a base case.
How Recursion Works
Every recursive function needs two things:
- 🛑 Base Case: When to stop (the smallest doll)
- 🔄 Recursive Case: Call itself with smaller input
Simple Example: Countdown
countdown(5) → print 5, call countdown(4)
countdown(4) → print 4, call countdown(3)
countdown(3) → print 3, call countdown(2)
countdown(2) → print 2, call countdown(1)
countdown(1) → print 1, STOP (base case)
Classic Example: Factorial
Factorial of 5 = 5 × 4 × 3 × 2 × 1 = 120
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)
Real-World Examples
- 📁 File Systems: Search folders within folders
- 🌳 Family Trees: Find all descendants
- 🔍 Search: Binary search in sorted lists
- 🎯 Sorting: Merge sort, quick sort
- 🗂️ JSON: Parse nested objects
Recursion vs Loops
Loop Approach: Repeat with counter
Recursive Approach: Break problem into smaller versions
Both can solve the same problems, but recursion is elegant for naturally recursive problems!
The Danger: Infinite Recursion
Without a base case, recursion never stops - like Russian dolls that go on forever! Always ensure you have a stopping condition.
When to Use Recursion
- ✅ Tree/Graph Traversal: Navigate hierarchies
- ✅ Divide and Conquer: Break big problems into smaller ones
- ✅ Backtracking: Try different paths (mazes, puzzles)
- ❌ Simple Loops: Use regular loops instead
The Call Stack
Each recursive call is added to a stack, like stacking plates. When the base case is reached, the stack unwinds, solving each level.
The bottom line: Recursion is a powerful technique where a function solves a problem by solving smaller versions of itself. Like Russian dolls, each level contains a smaller version until you reach the base case. It's elegant for certain problems but requires careful design!