Recursion
Learn how functions can call themselves to solve problems by breaking them into smaller pieces.
Recursion is when a function calls itself to solve a problem. It's like solving a puzzle by breaking it into smaller, identical puzzles.
"To understand recursion, you must first understand recursion."
Every recursive function has two essential parts:
1. Base Case
The condition that stops the recursion. Without it, the function would call itself forever!
2. Recursive Case
The function calls itself with a smaller/simpler version of the problem, moving toward the base case.
returnType recursiveFunction(parameters) {
// BASE CASE: When to stop
if (baseCondition) {
return baseValue;
}
// RECURSIVE CASE: Call itself with smaller problem
return recursiveFunction(smallerProblem);
}Key Insight
The recursive case must make progress toward the base case. If it doesn't, the recursion will never end!
Think of recursion like Russian nesting dolls (matryoshka):
- Each doll contains a smaller doll (recursive case)
- The smallest doll has nothing inside (base case)
- You must open each doll to reach the smallest one
- Then you close them in reverse order (returning values)
When a recursive function calls itself, each call is added to the call stack:
Going Down (Calling)
Coming Back Up (Returning)
Each call waits for its recursive call to return before it can complete. The stack grows until we hit the base case, then unwinds as values are returned.
Good for Recursion
- • Problems with recursive structure (trees, graphs)
- • Divide and conquer algorithms
- • When the problem naturally breaks into smaller same-type problems
- • When code clarity matters more than performance
Consider Iteration Instead
- • Simple loops or counting
- • When performance is critical
- • Very deep recursion (risk of stack overflow)
- • When iterative solution is just as clear