The Recursive Path Counter That Freezes at 25 by 25
A student in a Java programming class writes a recursive method to count unique paths across a grid for a game. The method is:
static long paths(int r, int c) { if (r == 0 || c == 0) return 1; return paths(r-1, c) + paths(r, c-1); }
It returns correct answers for 5×5 and 10×10 grids. The student's showcase project uses a 25×25 grid; the program freezes for over a minute and then throws StackOverflowError on some machines. The rubric awards 40% for correctness, 30% for efficiency, 20% for code clarity, and 10% for presentation. The student has two days, is proud of the recursion, and says 'It works on small grids.' The teacher must decide how to grade the current submission and what feedback to give. The class has covered loops and arrays but not memoization.
1. Diagnose the performance and stack problem. Estimate why 25×25 is so much worse than 10×10.
Read the worked answer
The recurrence branches into two calls at every cell and recomputes the same subproblems many times. The number of leaf calls is C(r+c, r). Because every non-leaf has two children, the total number of calls is 2C(r+c, r) − 1. A 10×10 input therefore uses 369,511 calls, while a 25×25 input uses 252,821,212,875,503 calls, approximately 2.53 × 10^14. That is roughly 680 million times more work, so a freeze is expected even on a fast machine. The recursive depth is only r + c = 50 at 25×25, so StackOverflowError is not explained by depth alone. The teacher should ask for the full stack trace, because the overflow may come from a second bug, a small stack setting, or a different test path. The primary diagnosis is exponential time from overlapping subproblems, not a mysterious hardware failure.
2. Propose a revision that preserves the recursive idea but fixes the failure, using only arrays and loops if necessary. Explain the trade-offs.
Read the worked answer
The least risky revision for a two-day deadline is an iterative dynamic-programming table. Use a one-dimensional array of length c+1, initialize every entry to 1 for the first row, then for each row i from 1 to r, loop j from 1 to c and update dp[j] = dp[j] + dp[j-1] from left to right. The final dp[c] is the count. This runs in O(r × c) time and O(c) space: 625 cells for 25×25, which is trivial. It preserves the same recurrence, just computed bottom-up instead of by repeated recursive calls.
If the student wants to keep recursion, add a memo array long[][] memo initialized to -1 and return the stored value when available. That is memoization; it also runs in O(r × c) time but uses O(r × c) space and introduces a new concept. The trade-off is that the iterative version is less elegant and does not look like the student's original recursion, but it is easier to debug under time pressure and meets the efficiency rubric. The teacher can frame it as 'same math, different execution order' rather than replacing the student's idea.
3. How should the teacher score the current submission against the rubric, and what feedback should be given? Justify.
Read the worked answer
The current submission should receive partial correctness, not full correctness, because the method is correct for small grids but does not meet the stated 25×25 requirement. A reasonable score is about 30 of 40 for correctness, 0 or very low of 30 for efficiency because the required input does not complete, full 20 of 20 for clarity because the base case and recurrence are readable, and 10 of 10 for presentation if the student can explain the idea. That is roughly 60%, with the exact efficiency score depending on how the rubric defines partial credit.
The feedback should be specific: 'Your base case and recurrence are correct, and that is why small grids work. The failure is not that recursion is wrong; it is that the same subproblems are recomputed exponentially many times. Here is the call-count comparison for 10×10 and 25×25. Replace the repeated calls with a table or memoization, keep your explanation of the recurrence, and resubmit within two days for efficiency credit.' This respects the student's work, names the actual defect, and gives a feasible path to improve the grade.