Recursion is the natural first step for many algorithmic problems. In interviews it’s valuable to:
- Show the recursive relation (base cases + recurrence).
- Move to memoization (top-down) to avoid exponential re-computation.
- Optionally present the bottom-up/tabulation or optimized version if asked.
Below are recursion-first solutions for the problems where recursion makes sense. Each snippet is self-contained and focused on the recursive idea + memoization where needed.
Scope note: I include recursion solutions for arrays/strings/DP/trees/graphs/linked-lists/backtracking problems. For problems that are fundamentally iterative/greedy/heap-driven (e.g., Dijkstra, Heap Top-K, Sliding Window max), recursion is either unnatural or inefficient — I’ll point that out and (where relevant) give recursive-style alternatives (e.g., DFS-based variants).
1. Fibonacci — Recursion + Memoization (warm-up)
import java.util.*;
public class FibMemo {
static int fib(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}
public static void main(String[] args) {
int n = 30;
int[] memo = new int[n+1];
Arrays.fill(memo, -1);
System.out.println(fib(n, memo));
}
}
2. Coin Change (min coins) — Top-down DP (recursion + memo)
import java.util.*;
public class CoinChangeTopDown {
static int INF = 1_000_000_000;
static int coinChange(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2); // -2 => uncomputed
int ans = dfs(amount, coins, memo);
return ans >= INF ? -1 : ans;
}
static int dfs(int rem, int[] coins, int[] memo) {
if (rem == 0) return 0;
if (rem < 0) return INF;
if (memo[rem] != -2) return memo[rem];
int res = INF;
for (int c : coins) {
res = Math.min(res, 1 + dfs(rem - c, coins, memo));
}
memo[rem] = res;
return res;
}
public static void main(String[] args) {
System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
}
}
3. Triangle Minimum Path — Top-down recursion + memo
import java.util.*;
public class TriangleTopDown {
static int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
Integer[][] memo = new Integer[n][n];
return dfs(0, 0, triangle, memo);
}
static int dfs(int r, int c, List<List<Integer>> t, Integer[][] memo) {
if (r == t.size() - 1) return t.get(r).get(c);
if (memo[r][c] != null) return memo[r][c];
int left = dfs(r+1, c, t, memo);
int right = dfs(r+1, c+1, t, memo);
memo[r][c] = t.get(r).get(c) + Math.min(left, right);
return memo[r][c];
}
}
4. Partition Array for Max Sum — Top-down recursion + memo
import java.util.*;
public class PartitionMaxSumTopDown {
static int[] arr;
static int K;
static int[] memo;
static int maxSum(int[] A, int k) {
arr = A; K = k;
memo = new int[A.length];
Arrays.fill(memo, -1);
return dfs(0);
}
static int dfs(int i) {
if (i >= arr.length) return 0;
if (memo[i] != -1) return memo[i];
int best = 0, maxVal = 0;
for (int len = 1; len <= K && i + len <= arr.length; len++) {
maxVal = Math.max(maxVal, arr[i + len - 1]);
best = Math.max(best, maxVal * len + dfs(i + len));
}
memo[i] = best;
return best;
}
public static void main(String[] args) {
int[] a = {1,15,7,9,2,5,10};
System.out.println(maxSum(a, 3)); // 84
}
}
5. Longest Increasing Subsequence (LIS) — Recursion + memo (O(n²))
import java.util.*;
public class LISRecursive {
static int lis(int[] nums) {
int n = nums.length;
int[] memo = new int[n];
Arrays.fill(memo, -1);
int best = 0;
for (int i = 0; i < n; i++) best = Math.max(best, dfs(i, nums, memo));
return best;
}
static int dfs(int i, int[] nums, int[] memo) {
if (memo[i] != -1) return memo[i];
int res = 1;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] > nums[i]) {
res = Math.max(res, 1 + dfs(j, nums, memo));
}
}
memo[i] = res;
return res;
}
public static void main(String[] args) {
System.out.println(lis(new int[]{10,9,2,5,3,7,101,18})); // 4
}
}
Note: interviewers expect you to know the O(n log n) solution, but top-down shows your DP thinking.
6. Longest Common Subsequence (LCS) — Recursion + memo
import java.util.*;
public class LCSTopDown {
static int lcs(String a, String b) {
int n = a.length(), m = b.length();
Integer[][] memo = new Integer[n][m];
return dfs(0,0,a,b,memo);
}
static int dfs(int i, int j, String a, String b, Integer[][] memo) {
if (i == a.length() || j == b.length()) return 0;
if (memo[i][j] != null) return memo[i][j];
if (a.charAt(i) == b.charAt(j)) {
memo[i][j] = 1 + dfs(i+1, j+1, a, b, memo);
} else {
memo[i][j] = Math.max(dfs(i+1,j,a,b,memo), dfs(i,j+1,a,b,memo));
}
return memo[i][j];
}
public static void main(String[] args) {
System.out.println(lcs("abcde", "ace")); // 3
}
}
7. Edit Distance (Levenshtein) — Recursion + memo
import java.util.*;
public class EditDistanceTopDown {
static int minDistance(String s, String t) {
Integer[][] memo = new Integer[s.length()+1][t.length()+1];
return dfs(0,0,s,t,memo);
}
static int dfs(int i, int j, String s, String t, Integer[][] memo) {
if (i == s.length()) return t.length() - j;
if (j == t.length()) return s.length() - i;
if (memo[i][j] != null) return memo[i][j];
if (s.charAt(i) == t.charAt(j)) {
memo[i][j] = dfs(i+1, j+1, s, t, memo);
} else {
int replace = 1 + dfs(i+1, j+1, s, t, memo);
int insert = 1 + dfs(i, j+1, s, t, memo);
int delete = 1 + dfs(i+1, j, s, t, memo);
memo[i][j] = Math.min(replace, Math.min(insert, delete));
}
return memo[i][j];
}
public static void main(String[] args) {
System.out.println(minDistance("horse", "ros")); // 3
}
}
8. 0/1 Knapsack — Recursive Memo
import java.util.*;
public class KnapsackTopDown {
static int knap(int[] wt, int[] val, int W) {
Integer[][] memo = new Integer[wt.length+1][W+1];
return dfs(0, W, wt, val, memo);
}
static int dfs(int idx, int remW, int[] wt, int[] val, Integer[][] memo) {
if (idx == wt.length || remW == 0) return 0;
if (memo[idx][remW] != null) return memo[idx][remW];
int skip = dfs(idx+1, remW, wt, val, memo);
int take = 0;
if (wt[idx] <= remW) take = val[idx] + dfs(idx+1, remW - wt[idx], wt, val, memo);
memo[idx][remW] = Math.max(skip, take);
return memo[idx][remW];
}
public static void main(String[] args) {
int[] wt = {10,20,30}, val = {60,100,120};
System.out.println(knap(wt, val, 50)); // 220
}
}
9. Subset Sum (recursion + memo)
import java.util.*;
public class SubsetSumTopDown {
static boolean subsetSum(int[] nums, int target) {
Boolean[][] memo = new Boolean[nums.length+1][target+1];
return dfs(0, target, nums, memo);
}
static boolean dfs(int i, int rem, int[] nums, Boolean[][] memo) {
if (rem == 0) return true;
if (i == nums.length || rem < 0) return false;
if (memo[i][rem] != null) return memo[i][rem];
boolean res = dfs(i+1, rem, nums, memo) || dfs(i+1, rem - nums[i], nums, memo);
memo[i][rem] = res;
return res;
}
public static void main(String[] args) {
System.out.println(subsetSum(new int[]{1,5,11,5}, 11)); // true
}
}
10. Longest Prefix-Suffix (LPS) — recursive helper for computing prefix function?
KMP’s LPS computation is naturally iterative (linear). A recursion version isn’t standard or helpful; use iterative O(m) approach in interviews.
11. Merge Two Sorted Lists — Recursive
public class MergeSortedListsRecursive {
static class ListNode {
int val; ListNode next;
ListNode(int v){ val=v; }
}
static ListNode merge(ListNode a, ListNode b) {
if (a == null) return b;
if (b == null) return a;
if (a.val < b.val) {
a.next = merge(a.next, b);
return a;
} else {
b.next = merge(a, b.next);
return b;
}
}
}
12. Add Two Numbers (linked lists) — Recursive
public class AddTwoNumbersRecursive {
static class ListNode { int val; ListNode next; ListNode(int v){val=v;} }
// wrapper to handle carry
static ListNode add(ListNode l1, ListNode l2) {
return addHelper(l1, l2, 0);
}
static ListNode addHelper(ListNode a, ListNode b, int carry) {
if (a == null && b == null && carry == 0) return null;
int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
ListNode node = new ListNode(sum % 10);
node.next = addHelper(a == null ? null : a.next, b == null ? null : b.next, sum / 10);
return node;
}
}
13. Reverse Linked List — Recursive (already covered earlier)
static ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
14. Tree Problems — recursive is natural
(a) Max Root-to-Leaf Sum (recursive)
int maxRootToLeaf(TreeNode root) {
if (root == null) return Integer.MIN_VALUE;
if (root.left == null && root.right == null) return root.val;
return root.val + Math.max(maxRootToLeaf(root.left), maxRootToLeaf(root.right));
}
(b) Vertical Order — can use recursive DFS to collect (node, row, col) then sort
// idea: collect List of Triples (col, row, val) via DFS, then group by col sorted
(Implementation omitted for brevity — DFS collects coordinates; final order determined by sorting/grouping.)
15. Number of Islands — recursive DFS (flood fill)
public class IslandsDFS {
public int numIslands(char[][] grid) {
int count = 0;
for (int i=0;i<grid.length;i++) for (int j=0;j<grid[0].length;j++)
if (grid[i][j]=='1') { dfs(grid,i,j); count++; }
return count;
}
void dfs(char[][] g, int i, int j) {
if (i<0||j<0||i>=g.length||j>=g[0].length||g[i][j]=='0') return;
g[i][j]='0';
dfs(g,i+1,j); dfs(g,i-1,j); dfs(g,i,j+1); dfs(g,i,j-1);
}
}
16. Word Search — recursive DFS backtracking (already covered earlier)
17. N-Queens — backtracking (recursive) (already covered earlier)
18. Topological Sort — DFS (recursive)
DFS postorder gives topological order:
void dfsTopo(int u, boolean[] vis, boolean[] onStack, List<List<Integer>> adj, Deque<Integer> st) {
vis[u] = true;
for (int v : adj.get(u)) if (!vis[v]) dfsTopo(v, vis, onStack, adj, st);
st.push(u); // postorder push
}
19. TSP / Bitmask DP — recursion + memo (already shown earlier)
20. When recursion is not the right tool
- Dijkstra / Prim / Kruskal — these are iterative/greedy/union-find algorithms; recursion is not standard and would produce poor performance or unnatural code.
- Heaps / Sliding Window Max / Monotonic Deque — iterative is canonical.
- Segment Tree / Fenwick Tree — implementations are typically iterative or recursive for tree-building, but the essence is data-structure oriented rather than pure recursion for problem solving.
✅ Final notes & interview tips (Recursion edition)
- Always state the recurrence out loud in interviews — it's the core of your reasoning.
- Identify base cases clearly and show why they stop recursion.
- Show memoization (top-down) quickly when naive recursion is exponential.
- Be ready to convert to tabulation if the interviewer asks for iterative or space-optimized solution.
- For trees & graphs, recursion + markers (visited) is natural — but account for recursion depth (use iterative variants or explicit stacks for very deep graphs).
- Be explicit about complexity: give time/space and improvements after memoization.
Top comments (0)