Recursion and the stack
A recursive method calls itself on a smaller input. The method needs a case that stops the descent, a smaller value on every recursive call, and a way to combine the result of the call with the work of this one. Without the first the recursion never ends, and the program dies of a stack that ran out.
A base case
factorial(5) is 5 times factorial(4), which is 4 times factorial(3), and so on down to factorial(1), which is 1 and stops. The last call is the base case: it returns without calling the method again.
The file Factorial.java also computes the same number with a loop, so the two results can be compared:
public class Factorial {
public static void main(String[] args) {
System.out.println("5! = " + factorial(5));
System.out.println("10! = " + factorial(10));
int total = 1;
for (int i = 1; i <= 5; i++) {
total *= i;
}
System.out.println("loop: " + total);
}
static int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
}
javac -Xlint:all Factorial.java
java Factorial
5! = 120
10! = 3628800
loop: 120
10! fits in an int, and so does 12!; 13! overflows, and the method would return a negative number without a warning, which is the overflow of lesson 009 in a new place.
Factorial
The recursive call is the last operation of the method apart from the multiplication, so the pending multiplications wait on the stack while the calls go down. For 5 the stack holds five frames at its deepest, and each frame holds the value of n of that call.
A loop does the same work with one frame and a variable. Which one to write is a question of what the problem looks like, not of speed: factorial reads naturally as a recurrence, and a traversal of a tree reads naturally as recursion even when a loop is possible.
Fibonacci
The Fibonacci sequence has two base cases, 0 and 1, and every later value is the sum of the two before it. Written as a direct recurrence, the method recomputes the same values many times: fib(5) calls fib(3) twice, and the count grows exponentially.
public class Fibonacci {
public static void main(String[] args) {
for (int i = 0; i <= 10; i++) {
System.out.print(fib(i) + " ");
}
System.out.println();
System.out.println("fib(10) = " + fib(10));
}
static int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}
javac -Xlint:all Fibonacci.java
java Fibonacci
0 1 1 2 3 5 8 13 21 34 55
fib(10) = 55
The output ends with a space before the newline, because every value is printed with a trailing space and the empty println() only ends the line. For a larger index the repeated work becomes the problem: the number of calls grows exponentially with the index, while a loop with two variables gives the same number in as many passes as the index.
The call stack
Every call pushes a frame that holds the parameters, the local variables and the return address, and every return pops one. The stack has a fixed maximum size, so a recursion that never reaches a base case exhausts it. The JVM reports that as a StackOverflowError, which is an Error and not an Exception.
public class StackOverflow {
public static void main(String[] args) {
try {
down(0);
} catch (StackOverflowError error) {
System.out.println("caught: " + error);
}
System.out.println("still running");
}
static int down(int depth) {
return down(depth + 1) + 1;
}
}
javac -Xlint:all StackOverflow.java
java StackOverflow
caught: java.lang.StackOverflowError
still running
The program catches the error and keeps going, which shows what the error is: a failure of the stack, not of the program logic. Catching it is a diagnostic tool, not a design; the fix is the base case or the smaller argument that was missing.
What recursion costs
Each call costs a frame, and the depth of the recursion is the number of frames at once. A recursion that is one call deep per element, as a list traversal is, costs as much stack as the list is long, and a very long list overflows where a loop would not. A recursion that splits, as fib does, costs time as well: the same subproblem is solved again and again.
The usual answers are a loop when the shape is a sequence, an explicit stack when the shape is a tree but the depth is unknown, and memoisation, which stores the result of a call and returns it instead of recomputing. The last one is a map keyed by the argument, and the map part of the course has the structure.
Exercises
- Add a call factorial(13) to Factorial.java and print the result. Which number do you get, and why?
- Write a recursive method that sums the numbers from 1 to n, then the same sum with a loop.
- Change the base case of Fibonacci to n < 1 and explain the output.
- Count the calls of fib(5) by adding a static counter that every call increments.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a recursive method need to stop?
Answer
A base case that returns without calling itself
The base case is the one that ends the descent; without it the stack runs out.
-
What does the JVM throw when the call stack is exhausted?
Answer
StackOverflowError
An exhausted stack is an Error rather than an Exception, because no ordinary handling can continue the calls.
-
What is the base case of
factorial(n)?Answer
n <= 1, which returns 1
The descent stops at 1, and 0! is 1 as well, so n <= 1 covers both.
-
What does this program print?
public class Q1 { public static void main(String[] args) { System.out.println(factorial(4)); } static int factorial(int n) { if (n <= 1) { return 1; } return n * factorial(n - 1); } }Answer
24
The calls multiply 4, 3, 2 and 1, so the result is 24.
-
What does this program print?
public class Q2 { public static void main(String[] args) { System.out.println(fib(6)); } static int fib(int n) { if (n < 2) { return n; } return fib(n - 1) + fib(n - 2); } }Answer
8
The sequence is 0, 1, 1, 2, 3, 5, 8, so the value at index 6 is 8.
-
What does this program print?
public class Q3 { public static void main(String[] args) { System.out.println(sum(4)); } static int sum(int n) { if (n == 0) { return 0; } return n + sum(n - 1); } }Answer
10
The method adds 4, 3, 2 and 1, and the call at 0 returns without calling again.
-
What does this program print?
public class Q4 { public static void main(String[] args) { try { down(0); } catch (StackOverflowError error) { System.out.println("caught"); } } static int down(int n) { return down(n + 1) + 1; } }Answer
caught
The recursion has no base case, the stack runs out, and the catch prints one line.
-
Why is the recursive Fibonacci slow for a large index?
Answer
It solves the same subproblems again and again
The number of calls grows exponentially because fib(n-2) repeats work already done under fib(n-1).
-
What happens if a recursive method calls itself with the same argument?
Answer
The stack fills and the JVM throws StackOverflowError
Nothing about the call is smaller, so the descent never reaches a base case.
-
Which structure is the natural fit for a recursive method?
Answer
A tree, where each node has smaller subtrees
A tree is defined in terms of smaller trees, so the method mirrors the data; sequences are usually loops.
The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.
Article author: Arthur Isaev