Tracing recursive methods

Tracing is not the preferred approach on the AP CS A Exam. This is true for recursive methods as well as all other code. Whenever possible, recursive methods should be analyzed. When it is necessary to trace, the technique below is effective.

Java uses a call stack to keep track of the sequence of active method calls. This approach can be used to trace recursive methods by hand on the AP CS A Exam. The technique works for any sequence of method calls. On the AP CS A Exam it is usually only worthwhile for tracing recursive methods.

Stack based recursive method tracing technique

  1. If there is more than 1 call to the method within the method, label each call.
  2. Place the first method call in an empty stack.
  3. Trace the method as usual.
  4. When a recursive call is made, note the call at which the calling method stopped and add the called method to the top of the stack. Begin tracing the called method.
  5. When a method call returns, note that on the stack. Record any value returned by that method call. Go back to the topmost method on the stack that has not yet returned.

Simple recursive method tracing example

What does mystery(5) return?

public int mystery(int b)
{
    if (b == 0)
        return 0;
    
    if (b % 2 == 0)
        return mystery(b - 1) + 3;
    else
        return mystery(b - 1) + 2;
}

Solution & comments

See the step by step trace of this method. Each step includes annotated code and the call stack at the end of the step. Explanations are included for selected steps.

The same trace is available with each step on its own page, starting with Step 1.

Comment on Tracing recursive methods

Additional recursive method tracing examples

Additional recursion resources