Chapter 7 — Reps
Conditioning, not grading. AI is OFF. Recursion is a thinking move — you can’t build the reflex by reading; you build it by writing.
For every recursion you write, say the base case out loud before you write the recursive case. Half the bugs in this chapter come from skipping that step.
Rep 1 — Factorial, Hand-Traced
Create Rep1.java (or start from Rep1.java):
public class Rep1 {
public static long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
public static void main(String[] args) {
for (int i = 0; i <= 6; i++) {
System.out.println(i + "! = " + factorial(i));
}
}
}Run. Then on paper, trace factorial(4) step by step the way the chapter shows. Confirm your trace lands on 24. Don’t skip the paper trace — the muscle memory of unwinding a recursive call by hand is the point.
Rep 2 — Forget the Base Case On Purpose
Modify Rep 1 to remove the base case:
public static long factorial(int n) {
return n * factorial(n - 1); // no base case
}Run factorial(5). Observe the StackOverflowError. Read the stack trace — note the ... N more line where Java truncates the absurd depth.
Now: put the base case back. Run again to confirm normal operation.
This is the single most important reflex of recursion — base case first. Feel the failure mode once, in your own code, so you recognize it forever.
Rep 3 — Power, Two Ways
Create Rep3.java with both pow and powFast from §7.3 (or start from Rep3.java):
public class Rep3 {
public static long pow(long x, int n) {
if (n == 0) return 1;
return x * pow(x, n - 1);
}
public static long powFast(long x, int n) {
if (n == 0) return 1;
if (n % 2 == 0) return powFast(x * x, n / 2);
return x * powFast(x, n - 1);
}
public static void main(String[] args) {
System.out.println("pow(2, 10) = " + pow(2, 10));
System.out.println("powFast(2, 10) = " + powFast(2, 10));
System.out.println("powFast(2, 30) = " + powFast(2, 30));
}
}Run. Confirm both produce the same answer for pow(2, 10). Note that powFast recursion depth for n = 30 is dramatically smaller — add a System.out.println("call " + n); at the top of each to see the call sequences side by side.
Rep 4 — GCD
Create Rep4.java (or start from Rep4.java):
public class Rep4 {
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
public static void main(String[] args) {
int[][] pairs = {{48, 18}, {100, 75}, {17, 13}, {1071, 462}, {0, 5}};
for (int[] p : pairs) {
System.out.println("gcd(" + p[0] + ", " + p[1] + ") = " + gcd(p[0], p[1]));
}
}
}Run. Verify by hand on gcd(48, 18) — it should reduce 48,18 → 18,12 → 12,6 → 6,0 → 6.
Note: this gcd assumes non-negative inputs. What happens with gcd(-48, 18)? Try it. Decide whether you’d add a guard.
Rep 5 — Naive Fibonacci (Be Patient)
Create Rep5.java (or start from Rep5.java):
public class Rep5 {
public static long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
for (int n : new int[]{10, 20, 30, 40, 42, 44}) {
long start = System.currentTimeMillis();
long val = fib(n);
long ms = System.currentTimeMillis() - start;
System.out.printf("fib(%d) = %d (%d ms)%n", n, val, ms);
}
}
}Run. Notice the runtime explodes between n = 40 and n = 44. fib(44) may take 5–10 seconds. Don’t run fib(50) unless you want to wait a minute. This is the cost of exponential recursion. Feel it once.
Rep 6 — Memoized Fibonacci
Create Rep6.java (or start from Rep6.java):
import java.util.HashMap;
import java.util.Map;
public class Rep6 {
static Map<Integer, Long> cache = new HashMap<>();
public static long fib(int n) {
if (n <= 1) return n;
if (cache.containsKey(n)) return cache.get(n);
long result = fib(n - 1) + fib(n - 2);
cache.put(n, result);
return result;
}
public static void main(String[] args) {
for (int n : new int[]{40, 50, 60, 70, 80, 90}) {
long start = System.currentTimeMillis();
long val = fib(n);
long ms = System.currentTimeMillis() - start;
System.out.printf("fib(%d) = %d (%d ms)%n", n, val, ms);
}
}
}Run. Note fib(90) returns in essentially 0 ms. Compare to Rep 5 — even fib(44) was slow there. Two new lines turned exponential into linear.
(Bonus: warning — fib(93) overflows long. Past that you’d need BigInteger, which Coding 2 doesn’t require.)
Rep 7 — Nested Map Printer
Create Rep7.java (or start from Rep7.java):
import java.util.*;
public class Rep7 {
@SuppressWarnings("unchecked")
public static void printNested(Map<String, Object> map, int indent) {
String pad = " ".repeat(indent);
for (Map.Entry<String, Object> e : map.entrySet()) {
System.out.print(pad + e.getKey() + ": ");
if (e.getValue() instanceof Map<?, ?> child) {
System.out.println();
printNested((Map<String, Object>) child, indent + 1);
} else {
System.out.println(e.getValue());
}
}
}
public static void main(String[] args) {
Map<String, Object> config = new LinkedHashMap<>();
config.put("name", "ChurchApp");
config.put("version", "1.0");
Map<String, Object> server = new LinkedHashMap<>();
server.put("host", "localhost");
server.put("port", 8080);
config.put("server", server);
Map<String, Object> db = new LinkedHashMap<>();
Map<String, Object> primary = new LinkedHashMap<>();
primary.put("host", "db1");
primary.put("port", 5432);
db.put("primary", primary);
config.put("database", db);
printNested(config, 0);
}
}Run. Confirm the indented output matches the structure of the config. Add a fourth nesting level (a secondary under database) and re-run.
Why LinkedHashMap here instead of HashMap? Because LinkedHashMap preserves insertion order. HashMap’s iteration order is undefined and changes with the implementation. Chapter 8 will explain — for now, if iteration order matters, use LinkedHashMap or TreeMap.
Rep 8 — Directory Walker by Hand
Create Rep8.java (or start from Rep8.java):
import java.io.IOException;
import java.nio.file.*;
public class Rep8 {
public static void findJavaFiles(Path dir) throws IOException {
if (!Files.isDirectory(dir)) return;
try (DirectoryStream<Path> stream = Files.newDirectoryStream(dir)) {
for (Path child : stream) {
if (Files.isDirectory(child)) {
findJavaFiles(child);
} else if (child.toString().endsWith(".java")) {
System.out.println(child);
}
}
}
}
public static void main(String[] args) throws Exception {
Path root = Path.of("."); // current directory
findJavaFiles(root);
}
}Run from the directory containing all your Coding 2 reps. Confirm it prints every .java file recursively. Compare to the built-in version:
try (var stream = Files.walk(Path.of("."))) {
stream.filter(p -> p.toString().endsWith(".java"))
.forEach(System.out::println);
}Same result. The hand-rolled version is the one you’d reach for if you needed custom logic per file or per directory. The Files.walk version is shorter and standard for the common case.
Rep 9 — Recursion vs. Iteration: Factorial
Take Rep 1’s recursive factorial and write an iterative version side by side:
public static long factorialIterative(int n) {
long total = 1;
for (int i = 2; i <= n; i++) total *= i;
return total;
}Test that both produce the same results for n = 0..10. Then write one sentence in a comment: which version reads more clearly, and why? For factorial, this is genuinely a judgment call — both are defensible. Practice forming a defensible opinion.
Rep 10 — Recursion vs. Iteration: Directory Walk
Now do the harder comparison. Take Rep 8’s findJavaFiles and try to write an iterative version using an explicit ArrayDeque as a stack (or start from Rep10.java):
import java.io.IOException;
import java.nio.file.*;
import java.util.*;
public class Rep10 {
public static void findJavaFiles(Path root) throws IOException {
Deque<Path> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Path dir = stack.pop();
if (!Files.isDirectory(dir)) continue;
try (DirectoryStream<Path> stream = Files.newDirectoryStream(dir)) {
for (Path child : stream) {
if (Files.isDirectory(child)) {
stack.push(child);
} else if (child.toString().endsWith(".java")) {
System.out.println(child);
}
}
}
}
}
public static void main(String[] args) throws Exception {
findJavaFiles(Path.of("."));
}
}Run. Same output. Now write a comment comparing this iterative version to Rep 8’s recursive one. Which one would you reach for first? Most people say the recursive one — because the iterative version is essentially simulating recursion by hand. That insight is the point of the rep.
Rep 11 — Break It On Purpose
Six recursion bugs. Apply, observe, fix.
- Write a recursion that forgets the base case. Observe
StackOverflowError. - Write a recursion whose recursive call doesn’t shrink the input (
return foo(n)instead offoo(n-1)). ObserveStackOverflowError. - Write Fibonacci without memoization and call
fib(45). Observe the wait. - Pretty-print a nested map but forget to recurse on nested maps. Observe the
{...}representation leaks through. - Write a directory walker that recurses on every child, not just directories. Observe the failure (probably an exception on a file, or an infinite recursion if you forgot to check).
- Memoize Fibonacci but use a new cache inside each call. Observe that the speed-up disappears.
Done? One Last Thing.
Open a fresh file. Without looking at any rep:
- Define a recursive
countLines(Path file)that, given a path, returns the number of lines in the file if it’s a regular file, and the total number of lines across all files recursively if it’s a directory. - Run it on your Coding 2 directory.
- Now write the iterative version using a
Deque. - Compare the two. Which feels right?
That’s the whole shape of Project 7’s Hard tier in miniature. If this rep works, you’re ready.
Up next: Project 7 — Project 7: Three Recursive Problems.