Trace what this recursive method computes and identify any termination problem; how would you reason about a recursive method's correctness?
answer
- Trace by substitution: wind down, then unwind
- Correctness = induction: base + inductive step
- Assume smaller calls are correct (inductive hypothesis)
- Termination = strictly shrinking measure to a reachable base
- Bugs: off-by-one base, non-shrinking call, missing edge case
basics
~20 sTo trace recursion, substitute the call by hand: replace each call with its body until you reach the base case, then combine the results on the way back. To check correctness, make sure the base case returns the right answer and that every recursive call moves the input closer to the base case.
solid answer
~50 sReasoning about a recursive method has two checks. First, correctness of the base case: for the simplest input, does it return the right answer directly? Second, correctness of the recursive step: assuming the recursive call returns the correct answer for a smaller input (the 'inductive hypothesis'), does combining it produce the right answer for the current input? This is essentially induction. To trace concretely, expand each call into its body, winding down to the base case, then unwind, substituting returned values back up. The termination check is separate but vital: every recursive call must move strictly toward the base case (smaller n, shorter list, smaller range), and the base case must be reachable for all valid inputs; otherwise you get infinite recursion and StackOverflowError. Common bugs are an off-by-one base case (e.g. n == 1 when n could be 0), a recursive call that doesn't shrink the input, or missing a base case for an edge input like an empty collection or negative number.
go deeper
Can trace a small recursion by substitution and spot an obvious missing or wrong base case.
Reasons about termination via a shrinking measure, identifies off-by-one and non-shrinking-call bugs, and handles edge-case base cases.
Articulates correctness as induction (base + inductive step) and termination separately, and reviews recursive code for both plus edge inputs.
Mentors on inductive reasoning and termination proofs, sets review standards for recursive code (edge cases, depth bounds), and identifies subtle combination/correctness bugs beyond termination.
## How to read/trace a recursive method Given a recursive method, you understand it by **substitution**: replace a call with the body it would execute, repeatedly, until you reach the **base case**, then **unwind** by plugging returned values back in. Consider: ``` static int f(int n) { if (n <= 1) return n; // base case return f(n - 1) + f(n - 2); // recursive case } ``` Trace `f(4)`: ``` f(4) = f(3) + f(2) f(3) = f(2) + f(1) f(2) = f(1) + f(0) f(1) = 1 (base) f(0) = 0 (base) => f(2) = 1 + 0 = 1 => f(3) = 1 + 1 = 2 => f(4) = 2 + 1 = 3 ``` So `f` computes the **Fibonacci** sequence (0,1,1,2,3,5,…). The 'winding down' reaches base cases; the 'unwinding' combines results back up. ## Reasoning about correctness: induction A recursive method is correct if two things hold — the same structure as **mathematical induction**: 1. **Base case is correct:** for the smallest/simplest input, the method returns the right answer *without* recursing. (Here, `f(0)=0`, `f(1)=1` — correct Fibonacci seeds.) 2. **Inductive step is correct:** *assuming* the recursive calls return the correct answer for **smaller** inputs (the **inductive hypothesis**), the way you combine them yields the correct answer for the current input. (Here, assuming `f(n-1)` and `f(n-2)` are right, `f(n-1)+f(n-2)` is the right Fibonacci value.) If both hold and the recursion always terminates, the method is correct for all valid inputs. ## Termination: a separate, mandatory check Correctness of the *answer* doesn't guarantee the method *finishes*. For termination: - Every recursive call must move **strictly toward** the base case (a decreasing 'measure': smaller `n`, shorter remaining list, narrower index range). - The base case must be **reachable for every valid input**, including edge inputs. Violations cause **infinite recursion** and a `StackOverflowError`. ## Common termination/correctness bugs - **Off-by-one base case:** base case `if (n == 1)` but the method can legitimately be called with `n == 0` (which then skips the base and recurses to `n == -1`, `-2`, … forever). - **Non-shrinking recursive call:** e.g. `return f(n);` or `return f(n - 0);` — the input never decreases. - **Missing edge base case:** no handling for an **empty** collection, **null**, or **negative** number when those are valid inputs. - **Wrong combination:** base case and termination fine, but the way results are merged is wrong (a *correctness* bug, not a termination bug). ## A checklist for writing one 1. Identify the base case(s) — the smallest inputs you can answer directly. Cover edge inputs (0, empty, null). 2. Write the recursive case assuming the recursive call already works for smaller inputs. 3. Verify each recursive call shrinks the input toward a base case. 4. Trace one small example by substitution to sanity-check. ## Key takeaways - Trace by substitution: wind down to base cases, unwind combining results. - Correctness = correct base case + correct inductive step (assume smaller calls are right). - Termination = strictly shrinking measure + reachable base case for all inputs. - Watch off-by-one base cases, non-shrinking calls, and missing edge-case handling.
- What does the method 'static int f(int n){ if(n<=1) return n; return f(n-1)+f(n-2); }' compute?The nth Fibonacci number (with f(0)=0, f(1)=1): 0,1,1,2,3,5,8,... f(4) is 3.
- A method's base case is 'if (n == 1) return 1;' but it is sometimes called with n == 0. What is the bug and the fix?For n == 0 the base case is skipped, so it recurses to negative n forever and overflows the stack. Fix the base case to 'if (n <= 1)' or otherwise handle 0 (and negatives) explicitly.
saying these in an interview costs you the question
- Checking only the base case while ignoring whether input shrinks
- Assuming a traced answer proves termination
- Forgetting edge-case base cases (empty/null/negative/zero)
- Trying to mentally trace deep recursion instead of reasoning inductively