← All patternsRecursion · template
Pattern · Recursion
Recursion
Solve the problem by solving a smaller version of it, with a base case that stops the calls.
Time Depends on the recursion tree · Space O(depth) for the call stack
Taught in Module 12: Recursion
Think of it like this
Russian dolls: to count them, open one and count the rest the same way, until you reach the smallest doll that doesn't open.
Clues that point here
- → The problem is defined in terms of itself (factorial, Fibonacci, trees)
- → Nested structures
- → Divide the input and combine results
Not this pattern when
- ✕ Depth can be very large (risk of stack overflow; iterate instead)
- ✕ Subproblems repeat (add memoisation: DP)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
int solve(int n) {
if (n <= 1) return baseValue(n); // base case: stop
return combine(n, solve(n - 1)); // trust the smaller call
}Common versions
- Factorial and power
- Reverse a string
- Tree traversals
- Merge sort
Practice problems with this pattern
12.1Fibonacci NumberEasymain pattern12.2Pow(x, n)Mediummain pattern12.3Reverse a String RecursivelyEasymain pattern12.4Tower of HanoiMediummain pattern12.5K-th Symbol in GrammarMediummain pattern