Recursion & Memoization
Learn to write recursion yourself, then turn it into memoized DP step by step. No memorising. Java only.
Most students memorise DP solutions and freeze when the question changes slightly. This module teaches the method instead: see what Java does on every call with an interactive visualiser, write recursion from a three-question recipe, draw the choice tree, then turn that recursion into memoization and a DP table in four mechanical steps. Every problem is derived the same way, in Java, with hidden tests.
- Picture exactly what Java does on every recursive call, using the call stack and the recursion tree
- Write a recursive method from scratch with the three-question recipe (promise, base case, smaller step)
- Solve subset, combination and permutation questions with pick/skip and backtracking
- Turn any recursion into memoization in four steps, then into a DP table when needed
- Recognise the six DP patterns that cover most coding tests, and avoid the common Java bugs
See it, then write it
What Java really does when a method calls itself, the three-question recipe, base cases, and two ways to carry the answer.
Start Here: Learn Recursion the Right Way
Why recursion feels hard, the one method this module teaches, and a 5-day plan if you are short on time.
How Java Runs Recursion
Every call is a new copy with its own variables. The caller waits and then continues. Code before the call runs on the way down, code after it runs on the way back up.
The 3-Question Recipe
Write recursion without tracing: say what the method returns, find the smallest case, and trust a smaller call. Plus how to choose base cases and why you should return the answer.
Trace the Output
15 predict-the-output questions on recursive Java code, every answer checked by running it: the before/after order, return values, accumulators, base-case bugs and how Java passes arrays and ints.
Sum From 1 to N
Return 1 + 2 + … + n. Use recursion, not a loop or the formula.
Reverse a String
Return "s" written backwards. Use recursion, not a loop or StringBuilder.reverse().
Sum of Digits
Return the sum of the digits of "n". Use recursion, no loops.
Palindrome Check
Return true if "s" reads the same forwards and backwards. Compare characters exactly, so "A" and "a" are different. Use two indices and don't build new strings.
Fast Power
Return xⁿ modulo 1,000,000,007. n can be as large as 10¹⁸, so going down one step at a time is far too slow. Halve n instead.
Tower of Hanoi
There are three pegs: 1, 2 and 3. Peg 1 holds "n" disks, biggest at the bottom. Move them all to peg 3:
Fibonacci Number
Fibonacci numbers start 0, 1, and each next one is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, … Return fib(n). Write it as plain recursion. It gets slow near n = 30, and chapter 3 shows why.
Choices and backtracking
Draw the decision tree first. Pick or skip, loops of choices, and undoing a choice to try the next one.
Draw the Tree: Pick or Skip
Most recursion questions are a list of choices. Draw the choice tree for a tiny input, read the state and the base case from it, then write pick-or-skip code. One tree answers four kinds of questions.
Backtracking: Choose, Explore, Undo
When a step has many options, loop over them inside the recursion: choose, explore, undo. Covers combination sum, permutations, skipping duplicates and stopping early.
Subsets
Given distinct numbers, return every subset, including the empty one and the full one. Any order is fine.
Count Subsets With Sum K
Count the subsets of positive numbers that add up to exactly "k". Subsets are picked by position, so equal numbers at different positions count separately. The empty subset has sum 0.
Combination Sum
Return every unique combination of candidates that adds up to target. Each number can be used many times. Order doesn't matter: [2, 2, 3] and [3, 2, 2] are the same. Any order of answers is fine.
Permutations
Return every ordering of the given distinct numbers. Any order is fine.
Generate Parentheses
Return every valid string of "n" pairs of brackets: every "(" is closed by a later ")". Any order is fine.
N-Queens: Count the Boards
Place n queens on an n × n chessboard so that no two attack each other: no two share a row, a column or a diagonal. Return how many ways there are.
From recursion to memoization
Spot repeated work, add a memo in four steps, and turn it into a table only when you need to.
Repeated Calls and the Memo Fix
Plain recursion often solves the same call again and again. See it happen, switch memo on, and learn the 4 steps that turn any recursion into memoized DP, plus the Java details that cause wrong answers.
From Memo to Table
The same DP as a loop instead of recursion: same array, base cases first, loop so that what you need is already filled, copy the recurrence. Then save memory with two variables.
Climbing Stairs
You climb a staircase of "n" steps, 1 or 2 steps at a time. In how many different ways can you reach the top?
Frog Jump
A frog starts on stone 0 and wants to reach the last stone. From stone "i" it can jump to i + 1 or i + 2. A jump from i to j costs |heights[i] − heights[j]|. Return the smallest total cost.
Frog Jump With K Steps
The same frog, but from stone "i" it can jump to any stone from i + 1 to i + k. Return the smallest total cost. If you worked out Frog Jump, this is a two-line change.
House Robber
Houses stand in a row, and house "i" holds nums[i] rupees. You can't take from two neighbouring houses. Return the most you can take.
Subset Sum
Return true if some subset of the positive numbers adds up to exactly "k". n can be 100, so 2ⁿ is far too slow. Use a memo.
DP patterns for coding tests
Grids, take/skip with a target, unlimited supply, two strings, and increasing subsequences.
Which DP Is It? A Pattern Map
Most test DP questions are one of six shapes. How to spot each one from the question, what its state is, and what its recurrence looks like.
DP on Grids
Count paths or find the cheapest path in a grid. The state is the cell, the choices are the moves, and the table fills row by row.
Unique Paths With Obstacles
A robot moves only right or down, from the top-left cell to the bottom-right cell. Cells with 1 are walls. Count the paths. If the start or the end is a wall, the answer is 0.
Take or Skip With a Target
The most common DP in tests: each item used at most once, and a target or capacity that shrinks when you take one. State (i, rem), two choices. Covers subset sum, knapsack and equal partition.
0/1 Knapsack
A bag holds at most "W" kg. Item "i" weighs wt[i] kg and is worth val[i]. Take each item at most once. Return the most value that fits.
Partition Equal Subset Sum
Can the array be split into two groups with equal sums? Every number goes into exactly one group.
Unlimited Supply: Coin Change
When an item can be used again and again, taking it keeps you on the same item. One small change to take-or-skip solves fewest coins and number of ways.
Coin Change: Fewest Coins
You have an unlimited number of coins of each value. Return the fewest coins that add up to exactly amount, or −1 if it can't be done.
Coin Change: Number of Ways
With an unlimited number of coins of each value, how many different combinations make exactly amount? Order doesn't matter: 1 + 2 and 2 + 1 are the same. Amount 0 has one combination (no coins).
Two Strings: LCS and Edit Distance
One pointer in each string. If the characters match, move both. If not, try each allowed move and keep the best. Covers longest common subsequence and edit distance.
Longest Common Subsequence
A subsequence keeps some characters in their order (you may skip any). "ace" is a subsequence of "abcde". Return the length of the longest subsequence that both strings share.
Edit Distance
Turn word1 into word2. Inserting, deleting or replacing one character costs 1. Return the fewest operations.
Increasing Subsequences and Cuts
Two shapes where a choice depends on more than the index: remember your last pick (longest increasing subsequence), or loop over where the next piece ends (word break).
Longest Increasing Subsequence
Return the length of the longest strictly increasing subsequence of nums. A subsequence keeps the order but may skip elements.
Word Break
Return true if "s" can be split into words from wordDict. A word may be used many times.
Exam kit
A one-page playbook, a practice set on finding the state and the recurrence, and a timed mock.
Exam-Day Playbook
The whole module on one page: the 10-minute method, the base-case cheat sheet, the pattern finder, quick debugging and the Java bugs that cost marks.
Find the State and the Recurrence
16 questions on the step most students skip: naming the state, the base case and the recurrence before writing any code.
Recursion & DP Mock Test
20 questions in 25 minutes: trace recursive Java code, spot bugs, estimate complexity and choose the right method, like the MCQ round of a placement test.