## 2 Visualization of Recursion
### Visualizations of Recursion in SRec  
In this article, we focus on the visualizations generated by the SRec animation system. SRec supports visualization and animation of recursion in any Java algorithm, with the only restriction of using primitive data types. Versions 1.0 and 1.1 of SRec provided three general views (namely, traces, the control stack, and recursion trees) [3]. Version 1.1 enhanced substantially its interaction facilities, as shown here. Finally, version 1.2 of SRec supports three additional visualizations, specific to divide-and-conquer algorithms [8]; the system is currently capable of simultaneously showing two views. This evolution is partially due to the results of usability evaluations it has been subject to. SRec is a program animation system that generates animations (semi)automatically. The user may load any file containing Java source code, and it is preprocessed. If the file contains any divide-and-conquer algorithms, the user must identify them in a dialog. Then, the user may launch any method invocation, and during its execution a trail of relevant events is generated. After completion, the user may freely interact with its visualization and animation, which is automatically generated from the trail. The user has available five visualizations for divide-and-conquer algorithms and three visualizations for general recursive algorithms. We do not describe here implementation details, as they can be found elsewhere [9]. In the rest of the article, we use the well-known function _fib_ for the Fibonacci series to illustrate recursive algorithms in general, and _mergesort_ for divide-and-conquer algorithms. The three general visualizations are briefly described:  
* _Recursion tree_. This visualization allows display of the complete history of a recursive process as a tree. The root corresponds to the initial invocation. The children of a node are the recursive calls that it has invoked, from left to right in chronological order. Leaves represent calls corresponding to base cases. Every node is displayed with two areas, where the top area contains input values of parameters and the bottom one the result of the invocation (if the method does not return any value, the output state of parameters can be displayed). For example, Figure 1(a) displays the computation state for _fib_ (5) where most recursive calls finished their execution, but the active call _fib_ (1) and pending calls _fib_ (3) and _fib_ (5). In SRec, two states are displayed for every invocation: immediately after the invocation entry, and immediately before the invocation exit. The node framed in black in Figure 1(a) is the active node, so its computation is close to exit. Nodes framed in red correspond to pending invocations. In the figure, input values have a blue background and output values have a green background. * _The control stack_. The control stack is an internal data structure of the virtual machine that makes possible the execution of programs with subroutines. In SRec, records of the control stack only contain input and output values, so they have the same structure as the nodes of recursion trees. The control stack initially contains the first invocation. On entry of a method invocation, a new record is pushed at the top of the stack, becoming the active record. This new record contains input values, but the output area is empty. On exit of a method invocation, the output area of the record at the top is filled with the call results and it is later popped. Figure 1 displays the control stack at the same instant as Figure 1. Visualizations of the control stack can be quite complex [10]. Notice however that the control stack, as displayed by SRec, is isomorphic to the rightmost branch of its associated recursion tree. * _Trace_. A trace is a textual description of the sequence of events that take place during the execution of an algorithm, here entry or exit of every method invocation.