Printer friendly version

Abstract
Designing visual representations for recursive algorithms has been addressed within a pedagogically-oriented framework for animating algorithms. We present a classification for choosing the kind of visual representation that is most helpful to students. The classification is based on the way the algorithm navigates through a data structure and manipulates data items within a data structure, and suggest strategies for visual representation that work within the categories of this classification. Further opportunities for tailoring representation derive from the shape of the data structure and particular forms of recursion, such as tail recursion. While there may be no single, general way to represent recursive algorithms, our classification is a
useful guide to picking an appropriate strategy for use when animating recursive algorithms for teaching purposes.

1. Introduction
The Algorithms in Action (AIA) project [14] uses multimedia animations of algorithms as a pedagogical tool to help students learn. Our target group of students is studying a second-year core curriculum subject on data structures and algorithms, where the concentration is on searching and sorting algorithms. The students are familiar with the concept of recursion, but have not yet been exposed to any but the simplest of algorithms.

Although several algorithm animations are available, especially for the simpler algorithms [4], few satisfied our need for pedagogically oriented animation. Notable exceptions are Gloor's CD companion [7] to a text on algorithms [5] and the collaborative active textbooks of Marc Brown [2, 3], neither of which fit well with our syllabus and choice of textbook [11].

Our aim in developing AIA was to find a general approach to presenting and animating algorithms and to implement a framework that could be used as the basis for presenting specific algorithms. The expectation was that interactive visual presentation would help students develop both an overall conceptual idea of how each algorithm works and a more detailed procedural understanding.

2. The Algorithms in Action Framework
The AIA framework consists of animation, pseudocode, and textual explanation, all coordinated, as previously reported [15]. A cursor traces the execution of the algorithm through pseudocode, while the animation displays a conceptual representation of each step. Students control the level of detail being displayed by expanding or contracting lines of pseudocode. At higher levels of abstraction the animation helps students to grasp the overall concept of an algorithm, while the more detailed views help them understand the workings of the algorithm at a procedural level. The level of detail in the animation, in the explanation, and in the pseudocode expand and contract synchronously.

About the authors...

3. Recursion
Representing recursive algorithms in ways that will be helpful to students has proven to be more challenging than designing representations for iterative algorithms. While initially we sought a general approach to the problem of displaying recursive algorithm, in practice, we found that the choice of most suitable representation depended on the particular algorithm being displayed.

The most appropriate visual representation for recursive algorithms was correlated with a classification based on how the algorithm navigates through and manipulates the data items within the data structure [13]. In this classification, one category of algorithms consists of those that traverse a static data structure (e.g. search), another category contains algorithms that manipulate items within an existing data structure (e.g. sort), and a third category contains algorithms that build a data structure (e.g. insert). Within these categories, it was sometimes useful to further subdivide based on additional criteria, such as tail recursiveness and data structure shape.

4. Code Tracing of Recursive Calls
In AIA, only one copy of the recursive function is shown in the pseudocode. As a recursive call is made, the pseudocode tracing restarts at the top of the function. Visual clues assist with clarity here, and most of our second-year students understand that when the pseudocode cursor jumps from the recursive call within the function to the top of the same function, this represents a new function call. This approach might not be suitable for beginning programmers, where it may be useful to pop up a new window for each recursive call [16].

5. Recursive Manipulation of Data Items within an Existing Linear Data Structure
In recursive sorting algorithms, such as quicksort and merge sort, the starting point is an array or linked list containing the data items to be sorted. The data structures are linear, and the algorithms use the classical divide-and-conquer approach, where the algorithm makes a number of recursive function calls to smaller and smaller parts of the data structure. During each recursive call, some data items are rearranged. For example, in quicksort, each function call partitions the data such that all items before a designated "pivot" element are smaller than (or equal to) the pivot, and all items after are larger (or equal). Two recursive calls are then made, one to the part of the array with the smaller elements, and another to the part of the array with the larger elements. The student's task is to learn what happens during each recursive call and to understand how the progression of recursive calls moves the sorting process through the data structure.

For these algorithms, where data items within an existing linear data structure are manipulated without the data structure changing its size or shape, we represent each recursive call by a horizontal line under the sequence of data items referred to in the recursive call (Figure 1). The value of each data item is represented by a vertical bar, similar to the representation used in the seminal algorithm animation video, "Sorting out Sorting" [1]. Our use of horizontal bars to underline the segment of the data structure being manipulated during the recursive call bears a similarity to the design used by Dershem and Brummond [6]. Additionally, different shades of color distinguish between the currently active call, calls on the function stack, and completed calls.

Quicksort animation applet.

6. Recursive Navigation through a Linear Data Structure
Searching through a dictionary abstract data type entails navigating through a data structure, searching for a data item with a particular key. Initially nothing is known about the location of the key. As the search progresses the subset of possible locations is narrowed down.

Where the data structure is linear, navigation can be represented by horizontal lines under the data items referred to in the recursive call. This is similar to the representation used for quicksort, except that the search narrows in scope as it progresses (Figure 2), since there is only one recursive call, instead of the two recursive calls made by each invocation of quicksort.

This representation can also be useful for an equivalent iterative coding as it gives the history of the search at a single glance, but is less natural.

7. Navigation and Data Manipulation in Non-linear Data Structures
Data structures for search often have a nonlinear tree structure, which makes visualizing the current subset of the data more challenging. For a tree structure, there are several different ways in which the current subtree can be shown. Given some constraints on the tree layout, a horizontal bar similar to the horizontal bars used in quicksort can underline the leaves of the current subtree (Figure 3a). Alternatively, a modified approach can enclose subtrees involved in recursive calls in polygons (Figure 3b). Less abstractly, a pointer to the root of the subtree can be shown (Figure 3c).

The choice of representation is influenced by the students' background. First year students might find it easiest to understand the algorithm where the entire subtree is outlined. Later year students would generally be able to understand the significance of a pointer to the root of the subtree. The pointer representation has the advantage of being closest to the recursive code, and students might find this representation assists them in following the pseudocode closely. The pointer representation, alone or in combination with other representations, may help students make the link between the algorithm code and progression through the data structure, conceptualizing the idea that the subtree whose root is being pointed to consists of all the data still under consideration. Horizontal bars under the data structure might be useful in cases where the data structure is complicated and an objective is to reduce clutter on the screen, and can highlight the similarities between different algorithms, such as searching a (balanced) binary search tree (Figure 3a) and binary search in an array containing the inorder traversal of the same tree (Figure 2).

8. Navigation Using Non-Tail Recursive Algorithms
Where code is tail recursive, the currently active function call narrows the search one step, while the rest of the searching is done in successive recursive calls. The tail recursive algorithm is very similar to an iterative while loop. Visual representation for both recursive and iterative codings must indicate which part of the data structure is under investigation. For a recursive implementation, it is natural for the display to indicate multiple subsets of the data, getting smaller as the search progresses through multiple recursive calls.

When the code is not tail recursive, there is work to be done upon returning from the recursive call. The location of the recursive call within the code is important because it determines what work is to be done upon return from the call. The pedagogical challenge here is to help students keep track of the point in the calling function where the recursive call is made, as well as how the navigation is progressing through the data structure.

For example, when navigating through a splay tree [11] "rotations" are performed after the return from the recursive call. Rotations are local operations on a small portion of the tree, intended to improve the overall balance of the tree. Because the place of the rotations within the algorithm may not be immediately obvious to a student just learning the algorithm, we supplement the main animation display with an abbreviated function stack (Figure 4). The aim of showing the function stack is to track the progress through the calling function, and to show the work still to be done after return from the recursive call. We are, in effect, combining two types of animation: animating the result of the program, in the tree, and simultaneously animating the state of the program in the function stack [8], to help students make the mental link between the two processes.

Splay tree applet.

9. Recursive Insertion into a Data Structure
Unlike navigation, which works on an existing data structure, insertion of items into a data structure involves major changes in the size and possibly the shape of the data structure. Accurate visual representation of recursive insertion requires depicting changes in the data structure both during the growth phase, when the correct insertion point is sought and recursive calls are added to the function stack, and during the shrinking phase, when the recursive calls return, the function stack shrinks, and the appropriate links within the data structure are made.

For relatively uncomplicated algorithms, representation can be straightforward. Taking the radix search trie as an example, insertion involves creation of one new external node and possibly one or more internal nodes, which must all be linked into the trie. In animating insertion here, we depict the growth stage of the algorithm, where decisions about the path and nodes are made, by tracing the path to the insertion point, leaving gaps for the links, which are still to be made. (Figure 5). During the shrinking phase of the insertion algorithm, the animation shows the links forming as the recursive calls return. Since the eventual shape of the subtree after insertion of the new data is not known at the time of the growth phase, the pointer representation is convenient.

(a)	(b)
(c)

(a)

(b)

(c)

Patricia tree applet.

10. Evaluation
Our evaluation of the effectiveness of AIA has so far concentrated on the ways in which students find the tool useful in their learning. To date we have not specifically evaluated how students learn recursive algorithms, as distinct from and how they learn iterative algorithms. Data has been derived from diverse sources, including detailed usage logs, questionnaires, controlled observation, and focus groups. Our observations indicate that students believe that the tool allows them to learn better and faster. Particularly telling was the automated logging, which showed significant usage over the semester -- an average of around 30 sessions per student in the most recent semester (Figure 7). There was an initial peak when the system was first introduced to the students and, quite significantly, a large peak before the examination. The two troughs in the graphs corresponded to project deadline, i.e. students are otherwise occupied. In the week prior to the examination alone, there was an average of 8 sessions per student. Students' perceptions that the tool helped them learn was apparently translated into the action of using the tool for at least part of their study time.

Variations were also seen in the different use that students made of the textual explanations. During controlled observation, little use was made of the text, yet the detailed logging shows that some students make heavy use of the explanations. This may be due to different student preferences, but another possibility is that students are more reluctant to take the time to read text while being observed. Research of others suggests that textual explanations are essential for effective learning in algorithm animation systems [12, 9].

To date we have not performed specific evaluation of the ways recursion is visualized in AIA. Based on our more general evaluation, it seems likely that looking in depth at how students use the tool to learn recursive algorithms will reflect the variety of students' preferences and will also suggest further ways in which we can enhance the animation framework to support different styles of learning.

11. Recursive, Iterative or Both?
Many algorithms can be implemented either recursively or iteratively. Because teachers and books generally show students only one implementation, the distinction between the algorithm at a very abstract level and its implementation is sometimes lost. We have speculated that students may find it helpful to look at the iterative version during the initial stages of learning an algorithm, then progress to the recursive version, which generally requires more abstract thinking. In this section we suggest a way in which stepwise refinement can be used to merge recursive and iterative versions of algorithms to aid understanding. We hope to implement and evaluate this idea in the future.

At higher levels of abstraction, with the pseudocode contracted, it is possible to describe many algorithms in an iterative style, even when they may be coded recursively. Lower levels, with more detail, can reveal whether recursion or an iterative looping construct is used. Combining multiple implementations at the highest levels would emphasize to the students that recursion and iteration are merely implementation strategies, a concept that students often miss.

As an example, we show an algorithm for red-black tree insertion. Red-black trees are a kind of balanced binary search tree. The insertion algorithm performs rotations, and also "splitting" operations, which manipulate data and determine what rotations are performed. Iterative insertion algorithms perform splitting and rotation as the tree is traversed from root to the leaf, where the data is eventually inserted [10], and can trivially be recoded as a tail recursive implementation, with the operations performed just before the recursive call. There are also left-recursive algorithms, where splitting and rotation are performed after the recursive calls return - effectively, as the tree is traversed from leaf back to root. Yet another alternative is middle-recursive [11], where splitting is performed during the traversal down to a leaf and rotation is performed during the upward traversal.

Figure 8a shows the algorithm pseudocode at a high level in an iterative style. Figure 8b gives a lower level, or expanded, view. The two for loops have been expanded to reveal that the code is actually middle-recursive. The pseudocode expansion also shows that adding data at a leaf is done via the previous recursive call. By emphasising the common elements between different algorithm variations, we hope the students will gain a deeper understanding of algorithms and the variety of ways they can be implemented.

(a)

(b)

12. Conclusion
While designing animations to help elucidate recursive algorithms to students, we found that some visual representations were more helpful than others. We noticed a correlation between the kind of visual representation that is most effective and the way data items are being manipulated in the data structure. We group the algorithms we have animated into three categories: those that navigate through an existing data structure; those that manipulate data items within a data structure; and those that insert data items into a data structure. Typically, a particular visual representation works well for different algorithms within one of these categories. Further subdivisions into the type of data structure, e.g. linear or non-linear, and the type of recursion, e.g. tail-recursive vs. non-tail-recursive, are useful in some instances. The choice among alternatives is sometimes dictated by the level of the students and the pedagogical aims. Given the multiplicity of situations and the multiplicity of learning styles, we suggest that there is no single "best" visual representation fo recursive algorithms.

13. Availability
Demonstration modules are available at http://www.cs.mu.oz.au/aia. Further modules are available for teaching purposes, on request.

An external link to www.cs.mu.oz.au/aia

14. Acknowledgments
We would like to thank the Teaching and Learning (Multimedia Education Technologies) Committee of The University of Melbourne for their generous financial support. We wish to thank Ka-Chi Cheung, Andrew Graham, and Tim Witham for programming, Vic Ciesielski for assistance with the figures, and numerous anonymous students for their feedback on modules under development.

15. References
[1] Baecker, R. Sorting Out Sorting. University of Toronto, Morgan Kaufmann, 1981.

[2] Brown, M., Najork, M., and Raisamo, R. A Java-based implementation of collaborative active textbooks. In VL97: Proceedings of the IEEE International Symposium on Visual Languages (1997), pp. 372-379.

[3] Brown, M. H., and Najork, M. A. Collaborative active textbooks: A web-based algorithm animation system for an electronic classroom. SRC Research Report, Systems Research Center (1996).

[4] Brummond, P. The complete collection of algorithm animations. Last accessed at URL http://www.cs.hope.edu/~alganim/ccaa on 4 September 2001.

[5] Cormen, T., Leiserson, C., and Rivest, R. Introduction to Algorithms. MIT Press, 1990.

[6] Dershem, H., and Brummond, P. Tools for web-based sorting animation. SIGCSE Bulletin 30: Proceedings of the 29th SIGCSE Technical Symposium on Computer Science Education, 1 (1998), 222-226.

[7] Gloor, P., Dynes, S., and Lee, I. Animated algorithms: A hypermedia environment for "Introduction to Algorithms", MIT Press, 1993. ISBN 0-262-57096-3.

[8] Kann, C., Lindeman, R. W., and Heller, R. Integrating algorithm animation into a learning environment. Computers Educ. 28 (1997), 223-228.

[9] Naps, T., Eagan, J., and Norton, L. JAHVÉ - an environment to actively engage students in web-based algorithm visualization. SIGCSE Bull. 32 (2000), 109-113.

[10] Sedgewick, R. Algorithms in C, 2nd ed. Addison-Wesley, 1990.

[11] Sedgewick, R. Algorithms in C, Parts 1-4, 3rd ed. Addison-Wesley, 1998.

[12] Stasko, J., Badre, A., and Lewis, C. Do algorithm animations assist learning? an empirical study and analysis. In Proceedings of the INTERCHI '93 Conference on Human Factors in Computing Systems (Amsterdam, 1993), pp. 61-66.

[13] Stern, L., and Naish, L. Visual representations for recursive algorithms. In Proceedings of the 33rd SIGCSE Technical Symposium on Computer Science Education (Cincinnati, 2002), pp. 196-200.

[14] Stern, L., Naish, L., and Sondergaard, H. Algorithms in action. http://www.cs.mu.oz.au/aia.

[15] Stern, L., Søndergaard, H., and Naish, L. A strategy for managing content complexity in algorithm animation. In ITiCSE99: Proceedings of the Fourth Annual SIGCSE/SIGCUE Conference on Innovation and Technology in Computer Science Education (1999), pp. 127-130.

[16] Wilcocks, D., and Sanders, I. Animating recursion as an aid to instruction. Computers Educ. 23 (1994), 221-226.

********** End of Document **********

MEJ multimedia team member assigned to this paper	Yue-Ling Wong