Frames and counts

Tracing recursion is frame discipline. For:

public static int f(int n) {
    if (n <= 0) { return 1; }
    return n + f(n - 2);
}

| frame | call | computes | returns | | ----- | ----- | --------------- | ------- | | 1 | f(5) | 5 + f(3) | 5 + 6 | | 2 | f(3) | 3 + f(1) | 3 + 3 | | 3 | f(1) | 1 + f(-1) | 1 + 1 | | 4 | f(-1) | base | 1 |

Unwinding: f(1)=2, f(3)=6, f(5)=11... wait — f(5) = 5 + f(3) = 5 + 6 = 11? Recheck: f(3) = 3 + f(1) = 3 + 2 = 5, not 6. f(5) = 5 + 5 = 10. This is exactly why you write the table — mental arithmetic lies; the table doesn't.

Two exam-standard counts:

• Call count: how many times is f invoked? One per frame: 4 frames above → 4 calls (including the base-case frame).
• Print order: statements BEFORE the recursive call run on the way down; statements AFTER run on the way up. print(n); f(n-2); print(n); prints 5 3 1 1 3 5 — down-sequence then mirrored up-sequence.

The up/down asymmetry is the whole trick: code after the call executes in reverse order of the calls, because frames unwind in stack order.