← Recursion · guided lesson
Recursion
the story
Recursion
Every tool here exists because something was too slow or broke without it. Here is what.
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 solved
Writing code for nested, self-similar data — expressions, lists of lists, trees — in the same shape as the data.
why it matters: without it
Nested data would need a hand-managed stack everywhere; a 5-line tree method becomes 25 lines of bookkeeping.
sources: McCarthy — Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (CACM, 1960) ↗ · Report on the Algorithmic Language ALGOL 60 (CACM, May 1960) ↗ · Maarten van Emden — How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semantics (2014) ↗
also in this chapter: The call stack · Memoization · Quadtree
the idea
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.
watch it
The call stack, frame by frame
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
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.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Naive Fibonacci — the exploding recursion tree
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
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ⁿ).
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Two parts, always: a base case that returns without recursing, and a recursive case that makes the input strictly smaller.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 3 of 8
Read it once. Say it out loud once. Bas.
The call stack stores one frame per active call (its parameters and local variables). Depth of recursion = extra space used.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
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ⁿ).
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Overlapping sub-problems (naive Fibonacci) make recursion exponential. Memoization — caching each answer — makes it linear. That's the doorway to dynamic programming.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Java has no tail-call optimization: every call pushes a frame, so very deep recursion throws StackOverflowError. Loops or an explicit ArrayDeque stack avoid it.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Backtracking is recursion that makes a choice, recurses, then undoes the choice — the engine behind "generate all" problems.
spot the pattern
When you see this, think this
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
+2 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- 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).
quick check
One question. No pressure.
What happens if a recursive method has no reachable base case?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Fibonacci Number
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Which two parts must every recursive method have?
Question 1: Which two parts must every recursive method have?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.