Notes › DSA
Recursion Basics
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem.
Every recursive function needs two parts:
- Base case — the smallest input, answered directly (stops the recursion).
- Recursive case — break the problem into a smaller one and call yourself.
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case: smaller problem
}
What happens in memory (the call stack)
Each call gets its own stack frame with its parameters and local variables. Calls pile up until the base case, then return one by one:
factorial(4)
└ 4 * factorial(3)
└ 3 * factorial(2)
└ 2 * factorial(1) → 1 (base case)
← 2 * 1 = 2
← 3 * 2 = 6
← 4 * 6 = 24
Too many frames (very deep recursion or a missing base case) → stack overflow.
How to think recursively (the "leap of faith")
- Decide what the function returns for input n.
- Assume it already works for smaller inputs.
- Use that answer to build the answer for n.
- Write the base case for the smallest input.
Example — sum of digits: sum(1234) = 4 + sum(123); base case sum(0) = 0.
def digit_sum(n):
return 0 if n == 0 else n % 10 + digit_sum(n // 10)
Classic examples
Power in O(log n) (fast exponentiation):
long long power(long long x, int n) {
if (n == 0) return 1;
long long half = power(x, n / 2); // solve the half once, reuse it
return n % 2 ? half * half * x : half * half;
}
Reverse a string: rev(s) = rev(s[1:]) + s[0].
Palindrome check: first and last characters equal, and the middle is a palindrome.
Print 1 to n (work after the call → printed in increasing order):
void print(int n) {
if (n == 0) return;
print(n - 1);
cout << n << ' ';
}
Move the cout before the call and it prints n down to 1.
Tower of Hanoi: move n−1 discs to the helper peg, move the largest, move n−1 on top → 2ⁿ − 1 moves.
def hanoi(n, src, dst, via):
if n == 0: return
hanoi(n - 1, src, via, dst)
print(f"move disc {n} {src} → {dst}")
hanoi(n - 1, via, dst, src)
Types of recursion
| Type | Meaning | Example |
|---|---|---|
| Head recursion | recursive call first, work after | print 1..n above |
| Tail recursion | the recursive call is the last thing done | factorial with an accumulator |
| Tree recursion | more than one recursive call | Fibonacci, subsets |
| Indirect | A calls B, B calls A | is_even / is_odd |
Tail recursion with an accumulator:
int fact(int n, int acc = 1) { return n <= 1 ? acc : fact(n - 1, acc * n); }
(C++ compilers may optimise it into a loop; Java and Python don't.)
Complexity of recursion
Time = number of calls × work per call. Space = maximum depth (the stack).
| Function | Calls | Time | Space |
|---|---|---|---|
| factorial(n) | n | O(n) | O(n) |
| power(x, n) fast | log n | O(log n) | O(log n) |
| naive fib(n) | ~2ⁿ | O(2ⁿ) | O(n) |
| subsets of n items | 2ⁿ | O(n·2ⁿ) | O(n) |
Draw the recursion tree to count calls.
Memoization: when the same subproblems repeat
Naive fib(5) computes fib(3) twice and fib(2) three times. Store answers:
long[] memo = new long[n + 1]; // filled with -1
long fib(int n) {
if (n < 2) return n;
if (memo[n] != -1) return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}
O(2ⁿ) → O(n). This is top-down dynamic programming (Dynamic Programming).
Recursion with arrays: pass an index, not a copy
def array_sum(a, i=0):
return 0 if i == len(a) else a[i] + array_sum(a, i + 1)
Slicing (a[1:]) copies the list each time → O(n²) for no reason.
Recursion vs iteration
| Recursion | Iteration | |
|---|---|---|
| Code | shorter for trees, backtracking, divide & conquer | better for simple loops |
| Memory | uses the call stack | O(1) extra |
| Risk | stack overflow when deep | none |
Python's default recursion limit is about 1000 — use iteration (or sys.setrecursionlimit carefully) for deep inputs.
Common mistakes
- Missing or wrong base case → infinite recursion.
- The problem doesn't get smaller (
f(n)callingf(n)). - Forgetting to
returnthe recursive result. - Recomputing the same subproblems (use memoization).
Practice
Recursion & Backtracking problems. Try: factorial, power, palindrome, sum of digits, print all subsets, permutations, N-Queens.
Interview one-liners
- Base case stops the recursion; the recursive case must make the problem smaller.
- Space complexity of recursion = maximum depth of the call stack.
- Memoization turns exponential tree recursion into polynomial time.
- Next: Backtracking.