Programming
What is Recursion?
Recursion is when a function solves a problem by calling itself on a smaller piece of the same problem, until it reaches a simple case it can answer directly. It's a powerful way to express problems that contain smaller copies of themselves.
See it, don’t just read it.
Watch a 2-minute lesson with voice + animation that explains recursion.
Key things to understand
- 1Every recursion needs a base case — the simplest input that stops the calls — or it runs forever.
- 2Each call works on a smaller version of the problem and trusts the recursion to handle the rest.
- 3Classic examples: factorials, the Fibonacci sequence, and traversing trees or folders.
- 4It often mirrors the structure of the data, making some solutions far shorter than loops.
Frequently asked questions
- What is a base case?
- The condition that stops the recursion — a small input the function can answer without calling itself again. Without it, recursion never ends.
- Is recursion better than loops?
- Neither is universally better. Recursion is cleaner for naturally nested problems; loops are often more memory-efficient. Many recursions can be rewritten as loops.
- What is a stack overflow in recursion?
- If recursion goes too deep (or never hits a base case), it exhausts the call stack memory and the program crashes with a stack overflow error.