Project 7 — Three Recursive Problems

“For from him and through him and to him are all things.” — Romans 11:36

Chapter: 7 — Recursion Due: End of Week 7 Submit: A link to your code — an OnlineGDB project URL or a public GitHub repo URL — with GcdSolver.java, JavaFinder.java, NestedPrinter.java, their tests, and README.txt. See Coding 1’s online-coding workflow appendix for the full workflow. Allowed tools: the Java compiler, JUnit, a non-AI editor, the textbook. Not allowed (Phase 1 — AI is OFF): AI assistants of any kind. Recursion is a thinking move; you cannot outsource it.

The Setup

You will solve three problems. Each one is a recursion that the chapter described, but you are writing them clean — three independent classes, with tests, and with clear separation between the public method (what the user calls) and any internal recursive helper (the actual recursion).

Senior engineers usually do this. The public-facing factorial method validates inputs and calls a private helper that recurses. The user never sees the helper. The validation never has to happen twice. This is good shape, and the project is designed to make you build it.

Setup

A starter zip is on the course portal. Everything in it is also available to download directly here (and the no-portal path below tells you how to rebuild the one tricky piece — the sample tree — by hand, no account required):

• sample_tree/ — a small directory tree containing seven .java files at various depths, for use by Problem 2. Download the whole folder from the companion code: browse and download sample_tree/. When you put it next to your code, refer to it as sample_tree/ (or wrap it in a data/ folder and refer to it as data/sample_tree/ — either works; just point your walker at wherever you actually placed it).
• sample_config.json (download sample_config.json) — a nested JSON config file, for use by Problem 3 (parse this into a Map<String, Object> however you like, or hand-build the map in Java if you prefer).
• tests/ — starter JUnit harnesses for each problem (browse and download tests/). They give you the imports, the class, and the first few “at minimum” cases; you finish the rest (the rubric wants at least five passing tests per problem).
• A README template (download README.template.txt) — fill in your tier, approach, and AI honesty line, then save it as README.txt.

What’s in sample_tree/ (and how to build it yourself, no account needed)

Problem 2’s walker needs a directory tree to recurse over. The provided one looks like this — seven .java files at depths 0 through 2, plus a few non-Java files as decoys your filter must skip:

sample_tree/
  App.java                         <- a .java file at the top level
  README.txt                       <- not Java; skip
  app/
    config.properties              <- not Java; skip
    model/
      Member.java
      Ministry.java
    service/
      AttendanceService.java
    util/
      Dates.java
      StringHelpers.java
  test/
    AppTest.java
  docs/
    notes.txt                      <- not Java; skip
    architecture.txt               <- not Java; skip

Walked recursively and sorted by path with Comparator.naturalOrder(), the seven files your findJavaFiles should return — relative to the tree’s root — are, in order:

App.java
app/model/Member.java
app/model/Ministry.java
app/service/AttendanceService.java
app/util/Dates.java
app/util/StringHelpers.java
test/AppTest.java

(Capital App.java sorts before the lowercase app/ directory — that’s ordinary lexicographic ordering, and it’s worth confirming you understand why before you assert on it.) The four non-.java files must not appear. That count of seven and that ordering are exactly what your Problem 2 test should assert against.

No portal, no account, no admin rights? You don’t need any of it. You can recreate this tree by hand in two minutes: make the folders shown above, then create each file with any content you like (the contents don’t matter to Problem 2 — only the names and the shape do). Or, if you’re working on OnlineGDB rather than locally, the comprehensive-test path in Medium tier (M3) builds an equivalent tree in code with Files.createTempDirectory, so you can skip the fixture entirely and still get full credit. Either way you’re never blocked on a download. See Coding 1’s online-coding workflow appendix for the full online-coding workflow.

You write:

• GcdSolver.java
• JavaFinder.java
• NestedPrinter.java
• Their test classes.
• Optionally for Medium: MemoFib.java or CoinChange.java.
• Optionally for Hard: an iterative version of one of the three.

Learning Targets

By completing this project, you will demonstrate that you can:

• Write a recursive method with a clean base case + recursive case structure.
• Separate a public validating method from a private recursive helper.
• Recursively walk a structured-data type (directory, nested map).
• Recognize when memoization buys you a meaningful speed-up.
• Articulate when iteration would be clearer than recursion (and the converse).

Normal Tier

Goal: Solve all three problems recursively. One class per problem. JUnit tests for each.

Problem 1 — GcdSolver

Implement int gcd(int a, int b) using the Euclidean algorithm, recursively. Two requirements:

• The public method handles validation: a and b must be non-negative. If either is negative, throw IllegalArgumentException with a message that names the bad input. gcd(0, 0) is defined as 0 by convention.
• The recursion is in a private helper or in the public method itself — your choice — but the recursion is the algorithm. No loops.

public class GcdSolver {
    public static int gcd(int a, int b) {
        // validation, then recursive case
    }
}

Tests (at minimum):

• gcd(48, 18) → 6.
• gcd(100, 75) → 25.
• gcd(17, 13) → 1.
• gcd(0, 5) → 5; gcd(5, 0) → 5; gcd(0, 0) → 0.
• gcd(-1, 5) throws IllegalArgumentException.

Problem 2 — JavaFinder

Implement List<Path> findJavaFiles(Path root) that recursively returns every .java file under root, sorted by path (so the output is deterministic for the test). Requirements:

• The walker is recursive. You may not use Files.walk for the recursion itself. (You may use it in a test to cross-check your answer if you want.)
• If root doesn’t exist, throw NoSuchFileException (or wrap an IOException you catch). Document the choice.
• If root is a regular file (not a directory), return a singleton list if the file ends with .java, otherwise an empty list. This is the smallest-input case worth handling.

public class JavaFinder {
    public static List<Path> findJavaFiles(Path root) throws IOException {
        // recursive walker
    }
}

Tests (at minimum):

• Run on sample_tree/ (the fixture from Setup, wherever you placed it). Confirm the count — seven .java files — and that the sorted relative paths match the list in Setup. None of the non-.java decoys may appear.
• Run on a single .java file. Returns a list of size 1.
• Run on a single non-Java file. Returns empty list.
• Run on a non-existent path. Throws the appropriate exception.

Problem 3 — NestedPrinter

Implement String pretty(Map<String, Object> data) that returns a string representation of the nested map with one entry per line, indented by depth (2 spaces per level). Nested Map<String, Object> values recurse. Scalar values (String, Integer, Boolean, Double) are printed as key: value.

public class NestedPrinter {
    public static String pretty(Map<String, Object> data) {
        // recursive renderer
    }
}

Tests (at minimum):

• A flat map of three scalars produces three lines with no indentation.
• A map containing one nested map produces a parent line followed by indented children.
• A two-level-nested map produces 4-space indentation at the deepest level.
• An empty map produces an empty string (or one trailing newline — your call, document it).
• A null value renders as key: null (don’t crash).

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. Memoized Recursion + Benchmark

Pick one of: Fibonacci or coin change (return the number of ways to make n cents from a list of coin denominations).

• Write a naive recursive version with no memoization.

• Write a memoized version using a HashMap cache.

• Write a small main that times both for inputs of size 20, 30, 35, 40 (Fib) or appropriate values (coin change).

• Output a tiny report:

  fib(30) naive: 12 ms, memo: 0 ms
  fib(35) naive: 130 ms, memo: 0 ms
  fib(40) naive: 1500 ms, memo: 0 ms

• One paragraph in your README explaining why the memoized version is so much faster — name the redundant subtree structure and how the cache eliminates it.

M2. NestedPrinter handles Lists too

Extend NestedPrinter.pretty to also handle List<Object> values:

servers:
  - host: db1
    port: 5432
  - host: db2
    port: 5432

Each list element prefixed with - . If the list element is itself a map, the map’s entries follow the dash on subsequent lines with consistent indentation. Add tests for at least: list of scalars, list of maps, empty list.

M3. Comprehensive JavaFinder tests

Build a synthetic directory tree of your own in setUp() (using Files.createTempDirectory and Files.createFile), populate it with a known set of files, run findJavaFiles, and assert against the known answer. This isolates your tests from any change to sample_tree/. Tear down the directory in tearDown().

Hard Tier (+up to 25% additional extra credit)

H1. Rewrite One as Pure Iteration

Pick one of the three Normal problems and rewrite it using only iteration, no recursion. The natural pick is JavaFinder — convert it to use an explicit ArrayDeque<Path> as a stack (or Queue<Path> for breadth-first; either is fine, document which).

Submit both versions side-by-side, plus a one-page comparison essay (comparison.docx) that addresses:

• Which version reads more clearly, and why?
• Which version handles deep directory trees better (think about stack depth)?
• Which version would you reach for in production code, and what would change your mind?

Honest “the recursive one reads better but the iterative one is safer for unbounded depth” answers earn full credit. Lazy “the iterative one is faster because no function calls” without evidence does not.

H2. Recursive JSON Pretty-Printer

Extend NestedPrinter to produce valid JSON output (instead of the indented text format from Normal). Indentation, commas in the right places, no trailing commas, quoted strings, JSON-escaped values. The output of pretty(data) should parse cleanly as JSON. Add a round-trip test: read data/sample_config.json, pretty-print, compare normalized output.

This is the cousin of Project 6’s JSON writer, but driven by recursion explicitly. Notice how natural the structure becomes when the data is recursive — the function shape and the data shape match.

H3. Mutual Recursion

Implement a tiny expression evaluator using two mutually-recursive methods:

• int parseExpression(String s) — evaluates expr + expr or expr - expr or a term.
• int parseTerm(String s) — evaluates term * term or term / term or a number.

Each calls the other when appropriate. Handle integer inputs only. Parentheses optional but nice. Add tests.

This is the smallest taste of parsing, which Coding 3 will treat fully. The point here is to see mutual recursion — two functions that call each other to walk a structure together.

Submission

Submit one URL via the course portal:

• OnlineGDB project link (recommended for Coding 2).
• GitHub repo link (optional).

What the linked project must contain

1. GcdSolver.java, JavaFinder.java, NestedPrinter.java.
2. Their test classes.
3. For Medium: MemoFib.java or CoinChange.java with benchmark output.
4. For Hard: the iterative version (H1), the JSON variant (H2), or the expression evaluator (H3).
5. README.txt with:

# Project 7 — Three Recursive Problems

**Tier targeted:**  Normal / Medium / Hard
**Features done:**  (list)
**Recursion-vs-iteration:**  (one paragraph on what you noticed)
**Memoization speedup observed:** (M1) Naive vs memo numbers
**What I learned:**  (one paragraph)
**AI usage:**  NONE — Phase 1.  Signed: <your name>

6. Reflection comment block at the top of GcdSolver.java.
7. The program left runnable — java GcdSolver, java JavaFinder, java NestedPrinter each demo their function on a built-in example.

Hints (Read Before You Begin)

• Base case first. Write the trivial-input answer before you write the recursive step. If you can’t articulate the base case in one sentence, you don’t yet understand the problem.

• Trust the recursion. Once you’ve written the base case and the recursive step that reduces toward it, do not try to “trace it in your head” before believing it works. Write tests; run them. The recursion will do the right thing.

• Validate at the public boundary, recurse internally. Don’t re-validate on every recursive call. Write a private gcdHelper if it helps you keep the public method tidy.

• Sort JavaFinder output before returning. DirectoryStream’s order is filesystem-dependent. Sorting (paths.sort(Comparator.naturalOrder())) gives you a deterministic answer your test can assert against.

• NestedPrinter is a string builder, not a printer. Build the result into a StringBuilder and return it. Don’t print directly — that makes it impossible to test. Your demo main can print the result.

• Read the iteration comparison rep (Rep 10). It’s the warm-up for the Hard tier essay.

What Mastery Looks Like (Beyond the Rubric)

A great Project 7 has methods that read like the problem definition. gcd(a, b) is two lines plus validation. findJavaFiles is a small recursive walker. pretty is a switch on the value’s type with a recursive case for the nested data. Nothing is convoluted because the thinking did the work; the code just expresses it.

A great Project 7 has tests that describe the behavior, not just exercise it. Names like gcd_handlesZeroLeftArgument are doing pedagogy on the reader. The tests are also the spec.

A great Project 7’s Hard-tier essay is honest. The honest answer to “iteration vs. recursion” is usually “recursion reads better but iteration is safer for very deep cases.” Writing that, and meaning it, is the mark of a thoughtful engineer rather than a doctrinaire one.

Coach’s Note — I have hired engineers off the strength of how they answered “when would you use recursion?” in interviews. The wrong answer is “always” or “never.” The right answer is “when the data is recursive, and when I have headroom on the stack.” If you can give that answer at the end of this project, you have learned something a lot of senior engineers haven’t.

When You’re Done

1. Run every test. All green?
2. Re-read your three public methods. Do they look like the problem definition? If they don’t, simplify.
3. For the Hard essay, read it out loud. Does it sound like you thought through this, or like a regurgitation of the chapter?
4. Submit.
5. Read Chapter 8. Midterm is next week — and the chapter introduces the collections you’ve been using all along.

A theological footnote. The part contains the whole. The Christian who reads Romans 12 (“we, being many, are one body in Christ, and every one members one of another”) meets, in the doctrine of the body, an idea that the mathematics of recursion also discovers — that smaller instances of the pattern bear the shape of the whole, and that the whole is constituted of them. The two truths are not the same truth, but they rhyme. That recognition — that the world we are programming has the structure it does, and that the structures of theology and the structures of computation echo each other — is one of the quieter gifts of doing this work as a Christian.

See you next week. The midterm is on Friday.