This problem can be easily solved using a stack. My explanation of Tracing recursive methods explains the technique.

Also see my complete 2009 AP CS A Multiple Choice solutions.

## Stack based trace of 2009 AP CS A Multiple Choice #40

2009 AP CS A Multiple Choice #40 Solution (as PDF)