These are the notes for Java episode 12. You will learn what recursion is (a method that calls itself), why a method with no stopping point crashes with a StackOverflowError, the two parts of every recursive method (base case and recursive case), what happens on the call stack while it runs, tree recursion with the staircase problem (Fibonacci numbers), why naive tree recursion explodes (1.4 billion calls, timed live), how memoization makes it instant, when a loop is the better choice, and what tail position means. Every example below runs as-is in the SyntaxPilot compiler, with its real output from javac 21 (timings vary from machine to machine and run to run).
Before you start, remember from episode 11: a method is a named block of steps; static int fact(int n) takes an int parameter n and returns an int. Every time a method is called, Java gives that call a frame on the call stack to hold its parameters and local variables.
The problem: what number am I in the queue?
You are in a long ration-shop queue and can't see the front. You ask the person ahead: "What's your number? I'll add one." They don't know either, so they ask the person ahead of them: the same question, on a queue one person shorter. Finally the person at the front says "I'm number 1" without asking anyone. That answer travels back, and each person adds 1, until it reaches you.
A big question, answered by asking a smaller copy of the same question, with someone at the end who answers directly. That is recursion.
Factorial: 5 friends on a chai stall bench
Five friends, one bench with five seats. How many seating orders? The first seat has 5 choices, then 4 friends are left for 4 seats: 5 × (ways for 4). Keep going: 5 × 4 × 3 × 2 × 1 = 120.
Multiplying a number by every whole number below it, down to 1, is its factorial, written 5!. Notice the pattern: 5! = 5 × 4!. The factorial of n is n times the factorial of n - 1.
The way we already know, a loop:
public class Main {
public static void main(String[] args) {
int n = 5;
int ways = 1;
for (int i = 1; i <= n; i++) {
ways = ways * i;
}
System.out.println(n + " friends, " + ways + " ways");
}
}
5 friends, 120 ways
It works, but it doesn't look like the idea fact(5) = 5 × fact(4).
The obvious attempt: a method that calls itself
public class Main {
static int fact(int n) {
return n * fact(n - 1);
}
public static void main(String[] args) {
System.out.println(fact(5));
}
}
A method that calls itself is called recursion (a recursive method). This one compiles, and then:
Exception in thread "main" java.lang.StackOverflowError
at Main.fact(Main.java:3)
at Main.fact(Main.java:3)
at Main.fact(Main.java:3)
... (the same line, 1024 times in all)
Why it crashed
fact(5)callsfact(4), which callsfact(3), thenfact(2),fact(1),fact(0),fact(-1),fact(-2)... nobody ever answers directly, so the calls never stop.- Each call can't finish: it waits for the next call's answer. Every waiting call keeps its frame (its own
n) on the call stack. - The call stack is a small, fixed area of memory. After thousands of frames it is full, and Java throws a
StackOverflowError: the stack overflowed.
The fix: base case + recursive case
| In the queue | In Java |
|---|---|
| The front person: "I'm number 1", no asking | Base case: if (n == 1) return 1; |
| Everyone else asks the person ahead (a shorter queue) | Recursive case: return n * fact(n - 1); |
| People waiting for an answer, each remembering their place | Call stack frames, one per waiting call |
- Base case: the smallest version of the problem, answered directly, with no more recursive calls. It is what stops the recursion.
- Recursive case: the method calls itself on a smaller problem (a step closer to the base case) and uses that answer.
public class Main {
static int fact(int n) {
if (n == 1) {
return 1;
}
return n * fact(n - 1);
}
public static void main(String[] args) {
System.out.println(fact(5));
System.out.println(fact(10));
}
}
120
3628800
Put the base case first, before the recursive call.
Inside the call stack: calls go down, answers come up
Make fact print when it starts and when it has its answer:
public class Main {
static int fact(int n) {
System.out.println("call fact(" + n + ")");
if (n == 1) {
return 1;
}
int r = n * fact(n - 1);
System.out.println("fact(" + n + ") = " + r);
return r;
}
public static void main(String[] args) {
System.out.println(fact(4));
}
}
call fact(4)
call fact(3)
call fact(2)
call fact(1)
fact(2) = 2
fact(3) = 6
fact(4) = 24
24
Real-life example: a stack of plates at a wedding buffet. Each new call is a plate put on top; the top plate is always removed first (last in, first out, which is why it's called a stack).
push pop (answers come back)
┌─────────┐
│ fact(1) │ base case → returns 1
├─────────┤
│ fact(2) │ waits ............ 2 * 1 = 2
├─────────┤
│ fact(3) │ waits ............ 3 * 2 = 6
├─────────┤
│ fact(4) │ waits ............ 4 * 6 = 24
└─────────┘
Each frame has its own n: there are four different n variables alive at the deepest point, one per frame.
Four rules for every recursive method
- A base case, answered without calling itself.
- Every call gets smaller, a step closer to the base case.
- Trust the smaller call (the "leap of faith"): assume
fact(n - 1)is right; don't trace every level in your head. - Use its answer to build yours:
n * fact(n - 1).
Tree recursion: the railway footbridge
You climb the footbridge stairs at a railway station, 1 or 2 steps at a time. How many different ways are there to climb n steps?
Think about the last move: you arrived either from step n - 1 (one step) or from step n - 2 (two steps). So:
ways(n) = ways(n - 1) + ways(n - 2)
ways(1) = 1 ways(2) = 2 (base cases)
These numbers (1, 2, 3, 5, 8, 13, ...), each the sum of the two before it, are the Fibonacci numbers. Because each call makes two recursive calls, the calls branch like a tree: this is tree recursion.
public class Main {
static long ways(int n) {
if (n <= 2) return n;
return ways(n - 1) + ways(n - 2);
}
public static void main(String[] args) {
System.out.println(ways(4));
System.out.println(ways(5));
System.out.println(ways(10));
}
}
5
8
89
(An if with a single statement may be written on one line without { }.)
The blow-up: 44 steps
Count the calls with a static variable (a variable that belongs to the class, outside every method, so all calls share it) and time it:
public class Main {
static long calls = 0;
static long ways(int n) {
calls++;
if (n <= 2) return n;
return ways(n - 1) + ways(n - 2);
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(ways(44) + " ways");
System.out.println(calls + " calls");
long ms = System.currentTimeMillis() - start;
System.out.println(ms + " ms");
}
}
1134903170 ways
1402817465 calls
2091 ms
1.4 billion calls for one answer.
ways(5)
/ \
ways(4) ways(3) ← solved here...
/ \ / \
ways(3) ways(2) ways(2) ways(1)
↑ ...and again here
/ \
ways(2) ways(1)
Why: the same smaller questions (
ways(3),ways(2), ...) are solved again and again. Each extra step roughly doubles the work. Growth where each step multiplies the work is called exponential; this is the exponential blow-up. 50 steps would take over half a minute.
Memoization: write the answer down
Real-life example: homework. If the same sum appears twice, you don't work it out twice: you write the answer in your notebook the first time and look it up next time.
In Java the notebook is an array, memo. Memoization = store each answer the first time it is computed, and return the stored answer on every later call.
public class Main {
static long[] memo = new long[100];
static long ways(int n) {
if (n <= 2) return n;
if (memo[n] != 0) return memo[n];
memo[n] = ways(n - 1) + ways(n - 2);
return memo[n];
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(ways(44) + " ways");
System.out.println(ways(90) + " ways");
long ms = System.currentTimeMillis() - start;
System.out.println(ms + " ms");
}
}
1134903170 ways
4660046610375530309 ways
20 ms
Each ways(k) is now computed once, so ways(n) needs about n calls instead of billions. 0 works as "not solved yet" here because no answer is ever 0. Memoization is the first step of dynamic programming, which comes later in the course.
| Version | Calls for ways(44) |
Time |
|---|---|---|
| Plain tree recursion | 1,402,817,465 | about 2 seconds |
| Memoized | about 85 | a few milliseconds |
Recursion vs loops
Even with a correct base case, recursion can be too deep:
public class Main {
static long sum(int n) {
if (n == 0) {
return 0;
}
return n + sum(n - 1);
}
public static void main(String[] args) {
System.out.println(sum(1000));
System.out.println(sum(100000));
}
}
500500
Exception in thread "main" java.lang.StackOverflowError
at Main.sum(Main.java:6)
at Main.sum(Main.java:6)
...
It would stop eventually, but 100,000 waiting frames don't fit on the stack. A loop needs no frames:
public class Main {
public static void main(String[] args) {
long total = 0;
for (int i = 1; i <= 100000; i++) {
total += i;
}
System.out.println(total);
}
}
5000050000
| Recursion | Loop | |
|---|---|---|
| Code | short, matches "smaller copies" problems | sometimes much longer for such problems |
| Memory | one stack frame per waiting call | no extra frames |
| Depth limit | a few thousand to tens of thousands of calls, then StackOverflowError |
none |
| Best for | trees, folders inside folders, staircase-style problems, divide and conquer | counting, sums, simple repeats |
Anything recursion can do, a loop can do too (sometimes with your own stack).
Tail position: a recursive call is in tail position when it is the very last thing the method does. return n * fact(n - 1); is not a tail call: after it returns, the method still multiplies by n. Some languages turn tail calls into loops automatically (tail-call optimization); Java does not, so deep recursion overflows either way.
Common mistakes (and the real error messages)
| Mistake | Real message | Why | Fix |
|---|---|---|---|
No base case: return n * fact(n - 1); |
Exception in thread "main" java.lang.StackOverflowError |
it never stops calling itself | add if (n == 1) return 1; first |
fact(0) with base case n == 1 |
java.lang.StackOverflowError |
0, -1, -2... never reaches 1 | if (n <= 1) return 1; |
Computing the answer but not returning it: int r = n * fact(n - 1); |
Main.java:7: error: missing return statement |
an int method must return a value on every path |
return r; |
int fact(13) |
no error, prints 1932053504 (wrong) |
13! = 6,227,020,800 doesn't fit in int |
use long (correct up to 20!) |
| Recursion 100,000 deep | java.lang.StackOverflowError |
too many frames, even with a base case | use a loop |
Plain tree recursion for big n |
no error, just extremely slow | the same subproblems are recomputed | memoize |
| Base case after the recursive call | StackOverflowError |
the call happens before the check | check the base case first |
Mini project: the lucky number of a car number plate
Many people like a "lucky number" on their car's number plate: add the digits, and keep adding until one digit is left. 4589 → 4+5+8+9 = 26 → 2+6 = 8.
n % 10is the last digit,n / 10drops the last digit.digitSum(n): a single digit is its own sum (base case); otherwise last digit +digitSumof the rest.lucky(n): a single digit is the answer (base case); otherwiselucky(digitSum(n)).
public class Main {
static int digitSum(int n) {
if (n < 10) return n;
return n % 10 + digitSum(n / 10);
}
static int lucky(int n) {
if (n < 10) return n;
return lucky(digitSum(n));
}
public static void main(String[] args) {
int plate = 4589;
System.out.println("Digit sum: " + digitSum(plate));
System.out.println("Lucky number: " + lucky(plate));
}
}
Digit sum: 26
Lucky number: 8
Try lucky(9999): 36 → 9.
Practice
power(2, 10)recursively:2^n = 2 × 2^(n-1), and2^0 = 1.- Count the digits of a number recursively (
4589→4). - Reverse a String recursively: last character + reverse of the rest (
chai→iahc). - Memoize
ways(n)and printways(80). - A countdown:
countdown(5)prints5 4 3 2 1 Liftoff!. - Check a palindrome recursively: compare the first and last characters, then the middle.
Solutions and hints
All of these go inside public class Main, above main.
java static long power(int base, int exp) { if (exp == 0) return 1; return base * power(base, exp - 1); } // power(2, 10) → 1024java static int countDigits(int n) { if (n < 10) return 1; return 1 + countDigits(n / 10); } // countDigits(4589) → 4java static String reverse(String s) { if (s.length() <= 1) return s; return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1)); } // reverse("chai") → iahc- Use the memoized
waysfrom these notes:ways(80)→37889062373143906, instantly. java static void countdown(int n) { if (n == 0) { System.out.println("Liftoff!"); return; } System.out.print(n + " "); countdown(n - 1); }java static boolean isPalindrome(String s) { if (s.length() <= 1) return true; if (s.charAt(0) != s.charAt(s.length() - 1)) return false; return isPalindrome(s.substring(1, s.length() - 1)); } // isPalindrome("madam") → true, isPalindrome("java") → false
Quick quiz
What does f(3) print?
static void f(int n) {
if (n == 0) return;
System.out.print(n + " ");
f(n - 1);
System.out.print(n + " ");
}
A) 3 2 1 B) 3 2 1 1 2 3 C) 1 2 3 3 2 1 D) 3 2 1 0 1 2 3
Answer
B) 3 2 1 1 2 3. Each call prints its n on the way down, waits for f(n - 1), then prints its n again on the way back up (top plate first). f(0) prints nothing.
Interview questions
- What is recursion? A method that solves a problem by calling itself on a smaller version of the same problem, until it reaches a base case answered directly.
- What happens if a recursive method has no base case? It keeps calling itself; frames pile up on the call stack until it is full and the JVM throws
java.lang.StackOverflowError. - Is
StackOverflowErroran exception you should catch? It is anError, not anException: it signals a serious problem (usually missing/unreachable base case or too-deep recursion). Fix the code instead of catching it. - Why is naive recursive Fibonacci slow? It recomputes the same subproblems; the number of calls grows exponentially (about 1.4 billion calls for n = 44 in our version).
- What is memoization? Caching the result of each subproblem the first time it is computed so later calls return it immediately. It turns exponential Fibonacci into linear time.
- Recursion or iteration? Recursion for naturally recursive structures (trees, nested folders, divide and conquer); loops for simple repetition or very deep repetition, since loops don't use stack frames.
- Does Java do tail-call optimization? No. A recursive call in tail position still uses a new stack frame in Java.
- What is stored in a stack frame? The method's parameters, its local variables, and where to continue in the caller when it returns.
Glossary
| Term | Meaning | Example |
|---|---|---|
| recursion | a method calling itself to solve a smaller copy of the problem | fact calls fact |
| recursive method | a method that uses recursion | static int fact(int n) |
| base case | the smallest case, answered directly with no recursive call | if (n == 1) return 1; |
| recursive case | the part that calls the method on a smaller problem | return n * fact(n - 1); |
| call stack | the memory area where Java keeps one frame per running method call | fact(4), fact(3), ... waiting |
| stack frame | one call's own box on the call stack: its parameters and local variables | each call's own n |
| last in, first out (LIFO) | the newest item is removed first | a stack of plates |
StackOverflowError |
the error Java throws when the call stack is full | no base case |
factorial (n!) |
n × (n-1) × ... × 1 |
5! = 120 |
| Fibonacci numbers | each number is the sum of the two before it | 1, 2, 3, 5, 8, 13 |
| tree recursion | each call makes two or more recursive calls | ways(n-1) + ways(n-2) |
| exponential | each extra step multiplies the work (here: roughly doubles it) | 1.4 billion calls for 44 |
| exponential blow-up | the run time explodes because the work grows exponentially | naive ways(44) |
| memoization | storing answers to reuse them instead of recomputing | memo[n] |
| dynamic programming | solving a problem by reusing answers to its smaller subproblems | memoized ways |
| static variable | a variable that belongs to the class, shared by all calls | static long calls |
| tail position | the recursive call is the very last thing the method does | return f(n - 1); |
| leap of faith | trusting the smaller call to be correct while writing the method | assume fact(n-1) works |
n % 10 / n / 10 |
the last digit / the number without its last digit | 4589 % 10 = 9, 4589 / 10 = 458 |
Summary
- Recursion is a method calling itself on a smaller copy of the problem.
- Every recursive method needs a base case (stops it) and a recursive case (gets smaller each time). No base case, or one that is never reached, means
StackOverflowError. - Calls go down the call stack (one frame each), answers come back up, last in, first out.
- Tree recursion (two calls per call) can explode exponentially; memoization stores answers so each one is computed once.
- Very deep repetition is safer as a loop: Java does not optimize tail calls.
Next episode: Basics project: a student marks system, using variables, loops, arrays, Strings, StringBuilder, methods and recursion together.