Recursion
Solve a big problem by trusting a smaller copy of itself — and know exactly where it stops.
▶ guided lesson⚡ 1-minute summary↻ 14 recall cards
before this: Big-O · Java Toolkit
01 · why it exists
Why this exists, and the weight it carries
since1960
Recursion
John McCarthy (Lisp); the ALGOL 60 committee, report edited by Peter Naur
Recursion was a mathematical idea first; 1960 is when two landmark languages built it in. In April 1960, McCarthy's Lisp paper built a whole language around recursive functions. One month later, the ALGOL 60 report allowed a procedure to call itself — through one short sentence added late, after a phone call to its editor, Peter Naur. In Naur's memory the caller was van Wijngaarden, "speaking also for" Dijkstra; in Dijkstra's, it was Dijkstra himself. Maarten van Emden later retold both versions. Almost every language since, Java included, lets a method call itself.
the problem it solvedWriting code for nested, self-similar data — expressions, lists of lists, trees — in the same shape as the data.
its jobs today
- File systems: folder size, copy-folder and delete-folder walk sub-folders recursively (or with an explicit stack).
- Compilers:
javacparses Java with a hand-written recursive-descent parser — one method per grammar rule, calling each other. - Trees everywhere: rendering the DOM, walking JSON, and every tree or graph DFS later in this course.
the weight it carries
Illustrative: a project folder 10 levels deep holding 10⁵ files. A recursive walk makes one call per folder and touches each file once — O(files + folders) — while the call stack never holds more than about 10 frames, one per level.
without it
Nested data would need a hand-managed stack everywhere; a 5-line tree method becomes 25 lines of bookkeeping.
when · why · how
- when
- The input is nested or branching (trees, folders, expressions), or the definition is self-similar (row n is built from row n − 1).
- why
- The code mirrors the data, so it's short and provable by induction. Cost: time = calls × work per call; space = depth — O(n) for a chain, O(log n) when halving.
- how
- A method with a base case (
if (n <= 1) return n;) and a call on a strictly smaller input; carry extra state (indices, accumulators) in aprivatehelper's parameters.
since1945–1960
The call stack
Alan Turing; Friedrich L. Bauer & Klaus Samelson; Edsger W. Dijkstra
Turing's 1945 design for the ACE computer used two standard routines, BURY and UNBURY, to save and restore subroutine return addresses in a last-in, first-out list — a stack in all but name. In March 1957 Bauer and Samelson filed a German patent on the stack principle (the "Kellerprinzip" — Keller means cellar); Bauer's 1988 IEEE Computer Pioneer Award cites him "for computer stacks". In 1960 Dijkstra's paper "Recursive Programming" showed how a stack runs recursive procedures: every call gets a fresh frame on top.
the problem it solvedLetting a method pause, call another method (even itself), and later resume exactly where it stopped, with its own local variables intact.
its jobs today
- Every Java method call pushes a frame (parameters, locals, return address) on the thread's stack;
returnpops it. - Stack traces: the trace you read when an exception is thrown is a printout of these frames, top first.
- Depth limits: each thread's stack has a fixed size, so runaway or very deep recursion ends in
StackOverflowError.
the weight it carries
Illustrative: the JDK 17 docs list a 1024 KB default thread stack on Linux/x64 and macOS. If one recursive frame took ~100 bytes, that's about 1024 × 1024 / 100 ≈ 10,000 frames — so a recursion 10⁵ deep can overflow where a loop never would. (Real frame sizes vary with the method and the JIT.)
without it
No method could call another and resume afterwards with its own variables — recursion would be impossible.
when · why · how
- when
- Whenever you state the space of recursive code, and whenever an input can make the recursion very deep (10⁴+ levels).
- why
- Space = deepest chain of waiting calls: O(n) for a chain, O(log n) for halving. The stack is far smaller than the heap, so too deep means
StackOverflowError. - how
- Count the deepest chain. If it can reach ~10⁴–10⁵, use a loop or an explicit
Deque<T> stack = new ArrayDeque<>()withpush/pop— it lives on the heap.
since1968
Memoization
Donald Michie
In a 1968 Nature paper, "'Memo' Functions and Machine Learning", AI researcher Donald Michie described functions that remember their earlier results. A memo function checks its table first; if the answer is there, it skips the work. Today's word memoization comes from his "memo" functions.
the problem it solvedRecursions that solve the same sub-problem again and again — exponential time turns into (number of distinct states) × (work per state).
its jobs today
- Top-down dynamic programming: keep the natural recursion, cache each state's answer.
- Caching any expensive pure function: same input → same output, so compute once and look it up afterwards.
the weight it carries
Illustrative: naive fib(30) makes 2·F(31) − 1 = 2,692,537 calls. With a memo it makes 2·30 − 1 = 59 calls — about 45,000× fewer, for the cost of 31 stored ints.
without it
Every DP recursion would stay exponential: naive fib(50) alone needs about 4·10¹⁰ calls.
when · why · how
- when
- The recursion tree repeats the same arguments (draw it for n = 5 and look for repeats) and the function is pure.
- why
- Time drops to states × work per state — fib goes from O(2ⁿ) to O(n) — paid for with O(states) memory for the table.
- how
- Small non-negative int states: an
int[]filled with-1viaArrays.fill. Sparse or composite states: aHashMapwithgetthenput(notcomputeIfAbsentaround a recursive call).
sinceearly 1970s · 1974
Quadtree
Allen Klinger; Raphael A. Finkel & Jon L. Bentley
Two early-1970s ideas share the name. Allen Klinger described the region quadtree: cut a picture into four equal squares, and keep cutting only the squares that aren't all one colour — the kind LeetCode 427 builds. (He called it a Q-tree.) In 1974 Finkel and Bentley published "quad trees" (Acta Informatica) to search records with two keys at once, like x and y: each stored point splits its area into four quadrants, like a binary search tree in 2D. Hanan Samet's 1984 ACM Computing Surveys article collected both and their many variants.
the problem it solvedFast search over two-dimensional data — points, regions, images — without scanning every cell.
its jobs today
- Map tiles: Bing Maps names each tile with a quadkey — one digit per zoom level, each picking one of four sub-tiles — so a tile's key starts with its parent's key.
- Images: a region quadtree stores a big single-colour area as one leaf instead of thousands of pixels.
- Game maps: a quadtree over the world lets collision checks look only at objects in nearby quarters.
the weight it carries
Illustrative: a 64 × 64 black-and-white grid with a single black cell. The tree splits only along that cell's path: 6 internal nodes + (6 × 3 + 1) = 19 leaves = 25 nodes, instead of 4,096 cells.
without it
Every 2D question — what's near this point, what colour is this region — would scan the whole grid.
when · why · how
- when
- 2D data with big uniform areas or uneven density: images, maps, game worlds, spatial lookups.
- why
- Uniform regions collapse into single leaves, and finding one cell walks a single root-to-leaf path — at most log₂ n + 1 nodes instead of scanning n² cells.
- how
- A
Nodewith four child references; build it recursively over(row, col, size), never copying sub-grids.
02 · plain english
The idea in 30 seconds
A recursive method solves a problem by calling itself on a smaller input, then using that answer.
Every recursion needs a base case (small enough to answer directly) and a recursive case that moves towards it.
Each call gets its own frame on the call stack; the frames pile up on the way down and resolve on the way back up.
picture this
File Explorer working out a folder's size: size of Projects = its own files + the size of each sub-folder — and each sub-folder answers the same question the same way. A folder with no sub-folders is the base case; the totals flow back up to the top.
03 · remember
What you must know
- Two parts, always: a base case that returns without recursing, and a recursive case that makes the input strictly smaller.
- The leap of faith: assume the call on the smaller input already works. Your only job is to use its answer for the current input.
- The call stack stores one frame per active call (its parameters and local variables). Depth of recursion = extra space used.
- Cost = number of calls × work per call. Draw the recursion tree: a chain is O(n), halving is O(log n), two branches per level is O(2ⁿ).
- Overlapping sub-problems (naive Fibonacci) make recursion exponential. Memoization — caching each answer — makes it linear. That's the doorway to dynamic programming.
- Java has no tail-call optimization: every call pushes a frame, so very deep recursion throws
StackOverflowError. Loops or an explicitArrayDequestack avoid it. - Anything recursive can be written with a loop + explicit stack, and vice versa. Pick recursion when the data is nested or branching (trees, choices); pick loops for simple linear walks.
- Backtracking is recursion that makes a choice, recurses, then undoes the choice — the engine behind "generate all" problems.
04 · see it
Play with it in 3D
Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.
The call stack, frame by frame
factorial(n): frames stack up until the base case, then each one finishes with a multiplication on the way back.
Naive Fibonacci — the exploding recursion tree
Red nodes are sub-problems that were already solved somewhere else in the tree. That waste is why it's O(2ⁿ).
Memoization collapses the tree
The memo array fills from small to large; every repeat becomes a one-step lookup, so only 2n − 1 calls remain.
Halving the input — O(log n) recursion
pow(x, n) asks for pow(x, n/2) once and squares it. The call chain is only as long as n has binary digits.
Recursion as a tree of choices (backtracking teaser)
Each call chooses "(" or ")". Choices that would break the rules are never explored.
05 · cost
Time & space, explained
| Time | Stack space | why | |
|---|---|---|---|
| factorial(n) | O(n) | O(n) | One call per value n, n−1, …, 1; all of them wait on the stack at the deepest point. |
| Naive fib(n) | O(2ⁿ) | O(n) | Two calls per call → the tree roughly doubles per level (tightly ≈ 1.618ⁿ). Depth is only n, so space stays linear. |
| Memoized fib(n) | O(n) | O(n) | Each n from 0..n is computed once (2n − 1 calls); the memo array and stack are both size n. |
| Iterative fib(n) | O(n) | O(1) | Same n additions, but just two variables and no call stack. |
| Fast power pow(x, n) | O(log n) | O(log n) | n halves every call, so there are about log₂ n calls — each waiting on the stack. |
| Reverse a linked list recursively | O(n) | O(n) | One call per node, and every call stays on the stack until the end is reached. |
| Generate all strings of length m from 2 choices | O(2ᵐ · m) | O(m) | 2ᵐ leaves, each copied in O(m); the stack holds one frame per character. |
| Calls / total work | Example | why | |
|---|---|---|---|
| f(n) calls f(n − 1) once, O(1) work | O(n) | factorial, reverse list | A single chain of n calls. |
| f(n) calls f(n / 2) once, O(1) work | O(log n) | fast power, binary search | You can halve n only log₂ n times before reaching 1. |
| f(n) calls f(n − 1) twice | O(2ⁿ) | Tower of Hanoi; naive fib (≤ this) | Each level doubles the number of calls: 1, 2, 4, … 2ⁿ. Naive fib calls f(n − 1) + f(n − 2), so it is bounded by this (tightly ≈ 1.618ⁿ). |
| f(n) calls f(n / 2) twice + O(n) work | O(n log n) | merge sort | log n levels, and every level does O(n) work in total. |
| Any recursion with memoization | O(states × work per state) | memo fib: n states × O(1) | Each distinct input is solved once; repeats cost O(1). |
06 · java
Raw vs Collections Framework
Recursion vs a plain loop
class Factorial { /** n! = n × (n−1)! and 0! = 1! = 1. */ static long factorial(int n) { if (n <= 1) return 1; // base case: stop here long smaller = factorial(n - 1); // trust the smaller call return n * smaller; // combine on the way back }}class FactorialLoop { /** Same answer, no call stack: one frame, one variable. */ static long factorial(int n) { long result = 1; for (int i = 2; i <= n; i++) result *= i; return result; }}- Both are O(n) time. The recursive one also uses O(n) stack frames; the loop uses O(1).
- Use
longfor factorials: 13! already overflowsint, and 20! is the largest that fits in along. - If a recursion only passes values down a straight line, a loop is usually simpler and safer in Java.
The hidden call stack vs an explicit ArrayDeque
record Folder(String name, int files, List<Folder> children) {} class CountRecursive { /** Files in this folder + files in every sub-folder. */ static int countFiles(Folder folder) { int total = folder.files(); // this folder's own work for (Folder child : folder.children()) { total += countFiles(child); // same problem, smaller input } return total; // no children → loop is skipped: that's the base case }}class CountWithStack { /** The same traversal with an explicit stack — no risk of StackOverflowError. */ static int countFiles(Folder root) { Deque<Folder> stack = new ArrayDeque<>(); // ArrayDeque, not the legacy Stack class stack.push(root); int total = 0; while (!stack.isEmpty()) { Folder folder = stack.pop(); total += folder.files(); for (Folder child : folder.children()) stack.push(child); } return total; }}- Recursion uses the JVM's call stack for you. An explicit
Dequedoes the same job on the heap, which is far larger — noStackOverflowErroron deep inputs. - Use
ArrayDequewithpush/pop/peek. The oldjava.util.Stackclass is synchronized and extendsVector— slower and discouraged. - The explicit-stack version may visit children in a different order. If order matters, push children in reverse.
Memoization: int[] vs HashMap
class Solution { public int fib(int n) { int[] memo = new int[n + 1]; Arrays.fill(memo, -1); // -1 means "not solved yet" return solve(n, memo); } private int solve(int n, int[] memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; // solved before → reuse memo[n] = solve(n - 1, memo) + solve(n - 2, memo); return memo[n]; }}class MemoWithMap { private final Map<Integer, Long> memo = new HashMap<>(); /** Climbing stairs: ways(n) = ways(n−1) + ways(n−2). Each n is solved once. */ long ways(int n) { if (n <= 1) return 1; Long cached = memo.get(n); if (cached != null) return cached; // already solved → O(1) long result = ways(n - 1) + ways(n - 2); memo.put(n, result); // NOT computeIfAbsent: recursive updates inside it throw return result; }}- When the inputs are small non-negative integers, an
int[]/long[]memo is fastest: no boxing, O(1) indexing. - Use a
HashMapwhen the state is sparse, negative, or a combination of values (e.g. aStringorListkey). - Don't use
computeIfAbsentwith a function that recursively updates the sameHashMap— since Java 9 it can throwConcurrentModificationException. Useget+put. - Fill the memo with a sentinel (
-1) that can never be a real answer, so 0 can be cached too.
Tail recursion — and why Java doesn't save you
class TailRecursion { /** Tail call: the recursive call is the very last thing — nothing waits for its result. */ static long factorial(int n, long acc) { if (n <= 1) return acc; return factorial(n - 1, acc * n); // Java still pushes a new frame (no TCO) } /** What a tail call *could* be turned into — in Java you must do it yourself. */ static long factorialLoop(int n) { long acc = 1; while (n > 1) { acc *= n; n--; } return acc; }}- A tail call is a recursive call that's the very last action — nothing is left to do after it returns.
- Some languages turn tail calls into loops (Scheme always; Scala for self-calls, with
@tailrecto guarantee it; Kotlin withtailrec). The JVM andjavacdo not, so the stack still grows by one frame per call. - In Java, if you write a tail-recursive method, you might as well write the loop — it's a mechanical rewrite.
| call | does | cost |
|---|---|---|
Deque<T> st = new ArrayDeque<>() | Explicit stack to replace deep recursion | O(1) per op (amortized) |
st.push(x) / st.pop() / st.peek() | Push, remove, look at the top | O(1) |
map.get(k) / map.put(k, v) | Read / write a memo entry | O(1) average |
Arrays.fill(memo, -1) | Mark every memo slot as "not solved yet" | O(n) |
sb.append(c) / sb.deleteCharAt(sb.length() - 1) | Make a choice and undo it while backtracking | O(1) amortized |
Integer.bitCount(x) | Number of 1-bits (used in K-th Symbol) | O(1) |
new Thread(null, task, "deep", 1L << 26) | Run deep recursion on a thread with a bigger stack (a hint to the JVM) | — |
java -Xss8m Main | JVM flag: bigger default thread stack size | — |
Nested / branching data (trees, folders, JSON)
→ Recursion
The code mirrors the shape of the data — short and easy to prove correct.
Linear walk over n up to 10⁵–10⁶
→ A loop
Same time, O(1) space, no StackOverflowError risk.
Deep tree/graph DFS (depth may reach 10⁵)
→ ArrayDeque explicit stack
Heap memory instead of the limited thread stack.
Recursion that repeats the same sub-problems
→ Memoization (int[] or HashMap)
Turns exponential time into states × work per state.
Generate all combinations / arrangements
→ Recursion + backtracking
Each call is one choice; undo it and try the next.
07 · recognise
Spot the pattern
The answer for n is defined using the answer for n − 1, n / 2, or a sub-part
Write the recurrence first, then the base case
Nested or tree-shaped input (trees, folders, expressions, nested lists)
Recursion on each child, combine the results
"Generate all", "list every", "all combinations / permutations / subsets"
Recursion with choices → backtracking
Same arguments show up again and again in the recursion tree
Add a memo → dynamic programming
Work from the end of a linked list back to the front
Recurse to the end, act while unwinding
Huge exponent / repeated multiplication (xⁿ, matrix powers)
Divide and conquer: halve n each call
08 · traps & tricks
Mistakes to avoid, tricks to use
traps
- Missing or unreachable base case → infinite recursion →
StackOverflowError. Check that every path shrinks the input towards the base case. - Forgetting to
returnthe recursive result (fib(n-1) + fib(n-2);withoutreturndoesn't even compile;helper(x);instead ofreturn helper(x);silently drops the answer). - Calling the same sub-problem twice:
pow(x, n/2) * pow(x, n/2)is O(n), not O(log n). Store it in a variable. - Exponential blow-up from overlapping sub-problems (naive Fibonacci). Spot repeats in the tree and memoize.
- Recursing over 10⁵ linked-list nodes or a skewed tree in Java can overflow the stack — prefer the iterative version or an explicit stack.
s.substring(1)ornew ArrayList<>(list)on every call copies O(n) data per level → O(n²). Pass indices instead.- Negating
Integer.MIN_VALUEoverflows (it stays negative). Widen tolongbefore-n. - Sharing a mutable
StringBuilder/Listacross calls without undoing the change after the recursive call (the classic backtracking bug).
tricks
- Write recursion in three lines of English first: base case, smaller problem, how to combine. Then code it.
- Chalo, dry-run karte hain — with the smallest inputs first (0, 1, 2). If those work and each call shrinks the input, the rest follows by induction.
- State the space cost out loud in interviews: "this recursion is O(n) deep, so O(n) stack space" — many candidates forget it.
- If an interviewer asks "can you do it without recursion?", reach for a loop with variables (linear) or an
ArrayDeque(branching). - Draw the recursion tree for n = 4 or 5. Count the nodes and the levels — that is the time complexity.
- Use a
privatehelper with extra parameters (indices, accumulators) and keep the public method signature clean.
09 · why & how
Questions you might be too shy to ask
How do I write a recursive function without getting lost in all the calls?
Don't trace every call in your head. Decide (1) the base case, (2) what smaller input to call yourself on, and (3) how to turn that smaller answer into yours. Then trust the smaller call — that's mathematical induction. Trace only small inputs to double-check.
How do I pick the base case, and how do I know it's enough?
Pick the smallest input you can answer without thinking: an empty range, n = 0, a null node. Then check every recursive call: does it always land on a base case? Fibonacci calls fib(n - 2), which can jump from 1 to −1, so it needs both 0 and 1 covered. if (n <= 1) return n; does exactly that.
What actually happens in memory when a method calls itself?
Each call gets a new stack frame with its own copies of the parameters and local variables. The caller pauses at the call line. When the callee returns, its frame is popped and the caller resumes exactly where it stopped. The simulation above shows this stack in 3D.
Does code written after the recursive call run before or after the deeper calls?
After. The line after the call waits until the whole deeper chain has returned. So print(n); f(n - 1); prints 3, 2, 1 (on the way down). And f(n - 1); print(n); prints 1, 2, 3 (on the way back up). Same calls, different moment.
When the base case says return, does the whole recursion stop?
No. return ends only the current call and hands its value to the caller one level up. That caller then continues from its own call line. factorial(1) returns 1 to factorial(2), which multiplies and returns 2 to factorial(3), and so on up to the top.
Recursion or a loop — which should I use in an interview?
Use whichever is clearer for the shape of the problem. Linear walks (sum an array, reverse a string): a loop. Trees, nested data, "generate all": recursion. Then mention the trade-off: recursion costs O(depth) stack space and can overflow for very deep inputs in Java.
Why do solutions add a private helper instead of calling the LeetCode method itself?
The method LeetCode gives you often has no room for the extra state you need. reverseString(char[] s) has no left and right. So the public method just calls reverse(s, 0, s.length - 1), and that private helper recurses with the indices. Simple hai: the helper's parameters are the "smaller problem".
Why does naive Fibonacci get slow so quickly?
Every call makes two more calls, so the number of calls nearly doubles with each +1 to n. fib(30) makes over 2.6 million calls, and most of them recompute small values — fib(5) alone is computed 121,393 times. Caching each answer once (memoization) brings it down to 59 calls.
What is StackOverflowError and how deep can Java recurse?
The JVM gives each thread a fixed-size stack (the JDK 17 docs list 1024 KB by default on Linux/x64 and macOS; on Windows it depends on virtual memory; -Xss changes it). Each call uses some of it, so depending on how big each frame is you get roughly thousands to tens of thousands of nested calls. Go deeper and the JVM throws StackOverflowError. It's an Error, not something you should catch in normal code — fix the depth instead.
Does Java optimize tail recursion like some other languages?
No. Neither javac nor the JVM performs tail-call elimination, so a tail-recursive method still uses one frame per call. If you need it to run in constant stack space, rewrite it as a loop yourself.
How do I find the time complexity of a recursive function?
Count the calls and multiply by the work done in each one. Drawing the recursion tree helps: a chain of n calls → O(n); halving each time → O(log n); two calls per level for n levels → O(2ⁿ). Divide-and-conquer recurrences like T(n) = 2T(n/2) + O(n) → O(n log n) (the Master theorem formalises this).
Is memoization the same thing as dynamic programming?
Memoization is top-down dynamic programming: keep the natural recursion, cache results. Bottom-up DP fills a table from the smallest sub-problems with loops (like the iterative Fibonacci). Same idea, different direction — you'll go deep on both in the DP chapter.
Pow(x, n): when n is odd, n / 2 drops the remainder. How is the answer still right?
Integer division rounds down here: 7 / 2 = 3. So x⁷ = x³ · x³ · x — the extra × x puts back the piece that was dropped. For even n there's nothing to put back: x⁸ = x⁴ · x⁴. That's why the code checks n % 2 before choosing half * half or half * half * x.
Swap Nodes in Pairs: why call swapPairs(second.next) before setting second.next = head?
Because second.next is your only arrow to the rest of the list (node 3 onwards). If you overwrite it first, the rest is lost. So: save the rest by recursing on it (head.next = swapPairs(second.next)), then point second back at head. Draw 1 → 2 → 3 → 4 and move one arrow at a time.
10 · practice
Interview problems
Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.
- #509
- #344Reverse StringEasyTCSBloombergAmazonMicrosoftGoogle+1
- #24Swap Nodes in PairsMediumBloombergMicrosoftUberAmazonGoogle+1
- #50
- #779K-th Symbol in GrammarMediumGoogleGoldman SachsMicrosoftAmazonBloomberg
- #427Construct Quad TreeMediumUber
Also practise this here
Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.
- #206Reverse Linked ListEasyin Linked Lists
Trust the recursion: reverse the rest, then hook the head on — its recursive approach has a call-by-call dry run.
- #21Merge Two Sorted ListsEasyin Linked Lists
"The smaller head comes first; the rest is a smaller merge" — a six-line recursive splice.
- #22Generate ParenthesesMediumin Backtracking
Recursion as a decision tree: two choices per call, pruned by the open/close counts.
11 · revise
The whole chapter on one screen
9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.
- what it is
A method that calls itself on a smaller input. Two parts: a base case that returns directly, and a recursive case that moves towards it.
- use it when
Nested or branching data (trees, folders, JSON), self-similar definitions (row n from row n − 1), and "generate all" problems.
- template
if (base) return answer;→smaller = solve(smaller input);→return combine(smaller);Then trust the smaller call. - cost
Time = calls × work per call. Space = deepest chain of calls. Chain → O(n) · halving → O(log n) · two calls on n − 1 → O(2ⁿ).
- trap
No reachable base case → frames pile up →
StackOverflowError. Java has no tail-call optimization, so depth 10⁴–10⁵ is risky. - trap
pow(x, n/2) * pow(x, n/2)makes two calls → O(n). Storehalfonce → O(log n). Same sub-problem twice = wasted work. - trap
Backtracking with a shared
StringBuilderorList: undo the change after the recursive call, or later branches see leftovers. - pro tip
Repeated sub-problems? Add a memo (
int[]filled with −1, or aHashMap) so each state is solved once. That's top-down DP. - pro tip
Too deep for the stack? Rewrite with a loop, or an explicit
ArrayDequestack that lives on the heap.
12 · recall
Flip, remember, repeat
Which two parts must every recursive method have?
Question 1: Which two parts must every recursive method have?
13 · check yourself
Quick quiz
What happens if a recursive method has no reachable base case?
factorial(5) is running and has reached factorial(1). How many factorial frames are on the stack?
Time complexity of naive recursive fib(n)?
`return pow(x, n/2) * pow(x, n/2);` (n even). What's its time complexity?
Recursive reverse of a 5000-node linked list. Extra space?
Does Java turn a tail-recursive method into a loop?
Memoized fib(n) makes how many calls (n ≥ 1)?
14 · learn more
A second teacher, if you want one
- ▶ playlistRecursion Playlist | Coding | Interview Questions | Algorithm | Tutorials ↗Aditya Verma · HindiBuilt on one idea: hypothesis, induction, base condition. You learn to trust the smaller call instead of tracing every frame.
- ▶ videoIntroduction to Recursion - Learn In The Best Way ↗Kunal Kushwaha · EnglishA slow, visual first lesson in Java: calls piling up on the stack, the base condition, and the recursion tree.
- ◈ visualizerRecursion Tree and DAG (Dynamic Programming/DP) ↗VisuAlgo (Steven Halim, NUS) · EnglishRun fib(n) and watch the recursion tree explode, then switch to the DAG view to see exactly what memoization saves.