Trace lab in Call Stacks and Recursion

Mission

Print pre-call and post-call events around the base case.

Learning outcome: Trace recursive entry and unwind order

Correctness contract

Invariant: Every recursive call moves strictly closer to a reachable base case.

Required technique: Use a recursive helper that records an entry event before the call and an unwind event after it.

Complexity target: time O(n); space O(n).

Input and output

Input: One integer n. Whitespace may be spaces or line breaks.

Output: Print the recursive entry, base, and unwind event tokens separated by single spaces. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is non-negative and small enough for the Java call stack.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Use a recursive helper that records an entry event before the call and an unwind event after it.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

2

Sample output

pre2 pre1 base post1 post2

Why the sample works: Visible walkthrough for the ordinary non-trivial path. pre events occur while frames are added, base marks termination, and post events appear during reverse-order unwinding. Input `2` therefore produces `pre2 pre1 base post1 post2`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.