Overview
A recursive function calls itself on a smaller input until it reaches a case simple enough to answer directly. Writing one well comes down to a single act of trust: assume the call on the smaller input already works, and only worry about combining its result with the current step. Programmers call this the "leap of faith".
Recursion is not just a coding style — it is how trees, graphs, backtracking and dynamic programming are naturally expressed. The cost model is the recursion tree: the total work is the sum over every call, and the extra space is the depth of the call stack.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Linear recursion (factorial, list sum) | O(n) time, O(n) stack |
| Halving recursion (fast power) | O(log n) |
| Merge sort | O(n log n) |
| Naive Fibonacci | O(2ⁿ) — O(n) with memoisation |
Patterns to recognise
Leap of faith
Use it for: Any problem defined in terms of smaller versions of itself.
Define what f(n) returns, handle the base case, express f(n) using f(smaller).
Halve the input
Use it for: Powers, binary search, divide and conquer.
Recurse on half the problem and combine in O(1) or O(n).
Recurse on choices
Use it for: Generating combinations, expression evaluation.
Each call branches on a decision; this grows into backtracking later in the roadmap.
Code template
def power(x, n):
if n == 0:
return 1.0
if n < 0:
return 1 / power(x, -n)
half = power(x, n // 2) # trust the smaller call
return half * half if n % 2 == 0 else half * half * x
double power(double x, long long n) {
if (n == 0) return 1.0;
if (n < 0) return 1.0 / power(x, -n);
double half = power(x, n / 2); // trust the smaller call
return (n % 2 == 0) ? half * half : half * half * x;
}
Common mistakes
- A missing or unreachable base case causes infinite recursion and a stack overflow.
- Calling the function twice on the same input (power(x, n/2) * power(x, n/2)) silently makes the algorithm exponential.
- Negating INT_MIN overflows in C++/Java — widen to long long first.
- Shared mutable state (a global list) must be restored after each call, or results leak between branches.
Quick check
Three questions on Recursion. Get all three right to earn +15 XP.
-
What happens when a recursive function has no base case?
Nothing ever stops the calls, so the stack grows until the program crashes.
-
Naive recursive Fibonacci, fib(n) = fib(n-1) + fib(n-2), runs in roughly:
Each call branches into two and recomputes the same values over and over.
-
How much extra memory does a recursion of depth d use, beyond its variables?
Every call that has not yet returned keeps a frame on the stack.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Fibonacci NumberLeetCode Easy +20
- Reverse StringLeetCode Easy +20
- Power of ThreeLeetCode Easy +20
- Pow(x, n)LeetCode Medium +40
- K-th Symbol in GrammarLeetCode Medium +40
- Different Ways to Add ParenthesesLeetCode Medium +40
Stuck on Recursion?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor