College CS Debugging Recursive Code

College CS recursion problems often fail for one of three reasons: the base case is wrong, the recursive call does not make progress, or the returned result is not combined correctly.

Scenario: recursive folder size

Imagine a method that computes the total size of a folder. A folder can contain files and subfolders. The recursive structure is natural because each subfolder is a smaller version of the original problem.

totalSize(folder):
    total ← size of files directly in folder
    FOR EACH subfolder IN folder.subfolders
        total ← total + totalSize(subfolder)
    RETURN total

Debugging with indentation

Print the recursive depth along with the current input. Indentation makes the call tree visible. Students can see whether recursion stops and whether returns happen in the expected order.

When memoization helps

Memoization helps when the same subproblem appears multiple times. It does not help much if every recursive path visits unique data only once.

Practice prompt

Trace a recursive method that counts paths in a small grid. Mark repeated states. Then decide whether memoization would reduce repeated work.