TRACING A RECURSIVE METHOD

The above diagram depicts the execution of the method call length with "jack" as the input argument. The diagram shows a series of recursive calls to the method length.After returning from each call to length, we finish executing the statement return 1 + length(...), by adding 1 to the result so far and then returning from the current call. The final result,4, would be returned from the original call. The arrow alongside each word return shows which call to length is associated with that result.For example, 0 is the result of the method call length("").After adding 1,we return 1,which is the result of the call length ("k") and so on.This process of returning from the recursive calls and computing the partial results is called unwinding the recursion.

The Run-Time Stack and Activation Frames

A recursive method can also be traced by showing what Java does when one method calls another.Java maintains a run-time stack, on which it saves new information in the form of an activation frame. The activation frame contains storage for the method arguments and any local variables as well as the return address of the instruction that called the method. Whenever a method is called, Java pushes a new activation frame onto the run-time stack and saves this information on the stack. This is done whether the method is recursive or non-recursive.

Diagram 5.2 (A) on the left depicts the activation frames on the run-time stack after the last recursive call (corresponding to length("")) resulting from an initial call to length("jack").At any given time, only the frame at the top of the stack is accessible,so its argument values will be used when the method instructions execute.When the return statement executes,the control will be passed to the instruction at the specified return address,and this frame will be popped from the stack (Diagram 5.2 (B)). The activation frame corresponding to the next-to-last call (length("k")) is now accessible.