The 3-Part Recursion Contract
1. Base Case
The smallest input that can be answered directly without recursion. Usually: empty, null, n=0 or n=1.
2. Recursive Case
Break problem into smaller subproblem of same type. Trust the function to solve the smaller version.
3. Return Value
What does this function return? Define this precisely — then the recursion writes itself.
C++
// Recursion template — fill in these parts
int solve(int n) {
// 1. Base case — answer is trivial here
if (n == 0) return 1; // or false, or 0, etc.
// 2. Recursive case — reduce problem size
int subResult = solve(n - 1);
// 3. Combine — use subResult to build answer for n
return n * subResult; // example: factorial
}
// Think: "If solve(n-1) works perfectly, what do I need to do for n?"
Call Stack & Space Complexity
Each recursive call adds a stack frame. Deep recursion = stack overflow. C++ default stack depth ≈ 10,000–100,000.
C++
// RECURSION DEPTH matters. This causes stack overflow for large n:
int factorial(int n) {
if(n<=1) return 1;
return n * factorial(n-1); // depth = n
}
// For linear chains (e.g. linked list DFS), consider iterative instead
// For trees: depth = O(h). For balanced tree: O(log n), skewed: O(n)
// HEAD vs TAIL recursion
// Head: recurse THEN process (postorder tree, merge sort)
// Tail: process THEN recurse (preorder tree, iteration-friendly)
void headRecursion(int n) {
if(n==0) return;
headRecursion(n-1); // recurse first
cout << n; // process after: prints 1,2,3...n
}
void tailRecursion(int n) {
if(n==0) return;
cout << n; // process first: prints n,n-1...1
tailRecursion(n-1); // recurse after
}
Interactive: fib(4) Call Tree
Trace the recursive calls for fib(4). Notice fib(2) is computed twice — this is the redundant work that memoization eliminates.
Practice Problems
#509Fibonacci NumberEasy
Compute the nth Fibonacci number (F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)).
Pattern: Pure recursion → O(2ⁿ). Recursion + memo → O(n). Bottom-up DP → O(n) time, O(1) space.
C++
// Memoized recursion
int memo[31] = {};
int fib(int n) {
if(n<=1) return n;
if(memo[n]) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
// Time: O(n) Space: O(n)
#344Reverse StringEasy
Reverse a character array in-place using recursion.
Pattern: Swap outermost characters, recurse on inner substring. Base: lo ≥ hi.
C++
void helper(vector<char>& s, int lo, int hi) {
if(lo>=hi) return;
swap(s[lo], s[hi]);
helper(s, lo+1, hi-1);
}
void reverseString(vector<char>& s) {
helper(s, 0, s.size()-1);
}
// Time: O(n) Space: O(n) stack
#779K-th Symbol in GrammarMedium
Row 1 = "0". Each subsequent row: replace 0→01, 1→10. Return kth symbol (1-indexed) in row n.
Pattern: Work backwards. K in row n comes from ⌈k/2⌉ in row n-1. If k is odd, same as parent. If even, flipped from parent.
C++
int kthGrammar(int n, int k) {
if(n==1) return 0;
int parent = kthGrammar(n-1, (k+1)/2);
bool isOdd = k%2;
return isOdd ? parent : 1-parent;
}
// Time: O(n) Space: O(n)
#50Pow(x, n)Medium
Implement pow(x, n) efficiently. x can be float, n can be negative.
Pattern: Fast exponentiation. If n is even: x^n = (x^(n/2))^2. If odd: x * x^(n-1). O(log n) recursive calls.
C++
double myPow(double x, long n) {
if(n==0) return 1;
if(n<0) { x=1/x; n=-n; }
double half = myPow(x, n/2);
return (n%2==0) ? half*half : x*half*half;
}
// Time: O(log n) Space: O(log n)
#95Unique Binary Search Trees IIMedium
Generate all structurally unique BSTs that store values 1..n.
Pattern: For each root value i in [lo, hi], generate all left subtrees from [lo, i-1] and right subtrees from [i+1, hi]. Combine all pairs.
C++
vector<TreeNode*> gen(int lo, int hi) {
if(lo>hi) return {nullptr};
vector<TreeNode*> res;
for(int i=lo;i<=hi;i++) {
for(auto l:gen(lo,i-1))
for(auto r:gen(i+1,hi)) {
TreeNode* root=new TreeNode(i);
root->left=l; root->right=r;
res.push_back(root);
}
}
return res;
}
vector<TreeNode*> generateTrees(int n) {
return gen(1,n);
}
// Time: O(Catalan(n)) Space: O(Catalan(n))
#241Different Ways to Add ParenthesesMedium
Add parentheses in different ways to evaluate a math expression string. Return all possible results.
Pattern: Divide and conquer. At each operator, split string into left/right. Compute all results for each part, combine with operator.
C++
vector<int> diffWays(string expr) {
vector<int> res;
for(int i=0;i<expr.size();i++) {
char c=expr[i];
if(c=='+'||c=='-'||c=='*') {
auto L=diffWays(expr.substr(0,i));
auto R=diffWays(expr.substr(i+1));
for(int l:L) for(int r:R) {
if(c=='+') res.push_back(l+r);
if(c=='-') res.push_back(l-r);
if(c=='*') res.push_back(l*r);
}
}
}
if(res.empty()) res.push_back(stoi(expr)); // pure number
return res;
}
#22Generate ParenthesesMedium
Generate all combinations of n pairs of well-formed parentheses.
Pattern: Recursive backtracking with pruning. Add '(' if open count < n. Add ')' if close count < open count. Backtrack when current string length = 2n.
C++
void gen(int open, int close, int n, string cur, vector<string>& res) {
if((int)cur.size()==2*n) { res.push_back(cur); return; }
if(open<n) gen(open+1, close, n, cur+'(', res);
if(close<open) gen(open, close+1, n, cur+')', res);
}
vector<string> generateParenthesis(int n) {
vector<string> res;
gen(0, 0, n, "", res);
return res;
}
// Time: O(4^n / sqrt(n)) — Catalan number Space: O(n)
#10Regular Expression MatchingHard
Implement regex matching with '.' (any char) and '*' (zero or more of preceding). Match must cover entire string s.
Pattern: DP (can also be solved recursively). dp[i][j] = true if s[0..i-1] matches p[0..j-1]. Key: '*' can mean zero uses (dp[i][j-2]) or one-more use (dp[i-1][j] if char matches).
C++
bool isMatch(string s, string p) {
int m=s.size(), n=p.size();
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
dp[0][0] = true;
for(int j=1;j<=n;j++) if(p[j-1]=='*') dp[0][j]=dp[0][j-2];
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) {
if(p[j-1]==s[i-1]||p[j-1]=='.') dp[i][j]=dp[i-1][j-1];
else if(p[j-1]=='*')
dp[i][j]=dp[i][j-2]|| // * matches zero
(dp[i-1][j]&&(p[j-2]==s[i-1]||p[j-2]=='.')); // * matches one more
}
return dp[m][n];
}
// Time: O(m*n) Space: O(m*n)
Leap of faith: The hardest part of recursion is trusting it. Write the contract ("this function returns X given Y"), write the base case, write the recursive case assuming the function already works. Don't trace the full call tree — just verify one step.
Deeper Understanding
The Recursive Mindset
The Contract Pattern: How to Write Any Recursive Function
When to Use Recursion
Problem has self-similar substructure
Trees, graphs, divide-and-conquer, parsing. Subproblem is the same type as the original, just smaller.
Need to explore all combinations or permutations
Backtracking — recursion with state undo. Generate parentheses, N-queens, subsets, permutations.
Problem is naturally expressed as f(n) = combine(f(n-1), ...)
Fibonacci, factorial, power, merge sort. Often converted to DP when subproblems overlap.
Tree or graph traversal
DFS is naturally recursive. Preorder, inorder, postorder all follow the same recursive template.
Overlapping subproblems detected
Add memoization (top-down DP). Same recursive structure but cache results to avoid redundant calls.
Common Misconceptions
"I need to trace the full call tree to write a recursive function"
Wrong. Trust the contract. Write solve(n) assuming solve(n-1) already works perfectly. The base case ensures it terminates.
"Recursion is always worse than iteration"
Wrong. For tree traversal and divide-and-conquer, recursion is cleaner and equally fast. Iteration shines when call depth is large (stack overflow risk).
"Recursive = slow"
Only without memoization. Naive fib is O(2^n) but memoized fib is O(n). Recursion + memoization = top-down DP.
Follow-Up Problems to Push Deeper
#46 Permutations (Medium)
Classic backtracking. Try each unused element at current position, recurse, undo choice. Shows the backtracking template clearly.
#78 Subsets (Medium)
Two recursive paths: include current element or skip it. Power set has 2^n elements — recursive tree has 2^n leaves.
#39 Combination Sum (Medium)
Backtracking with repeated elements allowed. Shows how to avoid duplicate paths: only pick from index forward.