A technique where a function calls itself to solve progressively smaller instances of the same problem. Recursion produces elegant, concise solutions for problems with naturally self-similar structure—tree traversals, fractals, file system navigation, and divide-and-conquer algorithms all rely on recursion as their natural expression.
Definition
A technique where a function calls itself to solve progressively smaller instances of the same problem. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that breaks the problem into a smaller version of itself.
💡 Intuition
Russian dolls—open one, find a smaller one inside. Repeat until you reach the smallest.
🎯 Core Idea
Every recursion needs a base case (when to stop) and a recursive case (how to continue).
Example
🌟 Why It Matters
Recursion produces elegant, concise solutions for problems with naturally self-similar structure—tree traversals, fractals, file system navigation, and divide-and-conquer algorithms all rely on recursion as their natural expression.
💭 Hint When Stuck
When writing a recursive function, first define the base case—the simplest version of the problem that can be answered directly. Then define the recursive case—how to reduce the current problem to a smaller version. Always verify that each recursive call moves closer to the base case.
Formal View
Related Concepts
🚧 Common Stuck Point
Without a base case, recursion never ends—the program crashes with a stack overflow error.
⚠️ Common Mistakes
- Forgetting the base case, causing infinite recursion and a stack overflow error
- Writing a recursive case that does not make the problem smaller, so the base case is never reached
- Not trusting the recursion—trying to trace every level mentally instead of trusting that the recursive call returns the correct result for the smaller problem
Common Mistakes Guides
Frequently Asked Questions
What is Recursion in CS Thinking?
A technique where a function calls itself to solve progressively smaller instances of the same problem. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that breaks the problem into a smaller version of itself.
When do you use Recursion?
When writing a recursive function, first define the base case—the simplest version of the problem that can be answered directly. Then define the recursive case—how to reduce the current problem to a smaller version. Always verify that each recursive call moves closer to the base case.
What do students usually get wrong about Recursion?
Without a base case, recursion never ends—the program crashes with a stack overflow error.
Next Steps
How Recursion Connects to Other Ideas
To understand recursion, you should first be comfortable with function and iteration. Once you have a solid grasp of recursion, you can move on to divide and conquer and merge sort.
💻 Animated Visualization Animated
Watch the function call itself, building a stack