RECURSIVE OBJECTS – AN OBJECT ORIENTED PRESENTATION OF RECURSION
Sher, David B
Generally, when recursion is introduced to students the concept is illustrated with a toy (Towers of Hanoi) and some abstract mathematical functions (factorial, power, Fibonacci). These illustrate recursion in the same sense that counting to 10 can be used to illustrate a for loop. These are all good illustrations, but do not represent serious applications of recursion.
Many of the most important applications of recursion occur on methods of lists, trees and graphs. These data structures are usually presented within the computer science sequences between computer science 2 and algorithms. In the ACM’s 2001 computing curriculum [1] these topics lie within PF3, Fundamental Data Structures, which in their curricula occur within CSlIl (first course in computing), CSl 12 (second course in computing) and CS201 (Algorithms) in both the imperative first and objects first curricula. At community colleges, the material in CSlIl and CS112 are often stretched into a three course sequence, Computer Science 1, Computer Science 2 and Data Structures. In my courses, this material is presented in Computer Science 2 and in Data Structures. This paper demonstrates an alternative approach to recursion.
A. TRADITIONAL APPROACH TO RECURSION
Most current texts present recursion procedurally. They translate algorithms from a procedural language like C or Pascal into an object oriented language. For example, in Malik and Nair’s Data Structures using Java [2], the code in code segment 1 prints a linked list in reverse order. This code could have been written in C or Pascal, and it fits the procedural rather than the object oriented paradigm. In Carrano and Savitch’s Data Structures and Abstractions using Java [3, p. 237] almost the same code is presented, but the name of the method and the node type is different. In all of these examples, the recursion is controlled through method parameters.
However, we can take advantage of the power of object oriented programming to present a version of recursion that combines recursive data with recursive methods. Thus, the recursion will be built into the data structures themselves and the advantages of object oriented programming will be apparent with this approach to recursion.
B. RECURSIVE OBJECTS
This paper presents an approach to recursion where an object has a “has a” relationship with an object of the same type. Thus, the objects are defined recursively. Code segment 2 defines a list that contains a list recursively. Notice that the print method takes no parameters at all, but still recourses through the list. This is because the List object itself is recursive and the methods follow the recursion implicit in the object.
The List type of code segment 2 is similar to the basic list type of the LISP language with the item being the car of the list and rest being the cdr. An empty list is the same as the NIL item in LISP. A List always starts out empty and becomes not empty when items are placed within it. Lists are traversed recursively, as exemplified by the print method of code segment 2.
C. TEACHING RECURSION WITH RECURSIVE OBJECTS
In recursive objects, recursion occurs when a method calls the same method, but from a different object. For example, in a binary tree the prefixPrint method would call left.prefixPrintQ and right.prefixPrintQ (see code segment 3). This is easier to illustrate than a method calling itself with different parameters. However, the recursive objects themselves can be difficult to explain.
Explaining recursive objects is required to explain trees and other recursive structures, even if the objects are not defined recursively. These methods can be explained by having each student in a class represent a subList or subTree as shown in code segment 3. When students perform their methods, they are simulating an object (so they have methods). Students can now see that by acting in concert how the original method is performed, and how it uses the methods from the contained objects to compute the correct result.
The code for recursive methods is simpler when recursive objects are used. Code segment 4 illustrates an implementation of a search tree in Java.
Note how the three defining methods of the Search Tree: insert, find and orderedPrint, are simplified.
* No extra parameters are necessary.
* Rather than having a method that the user calls and a separate recursive helper method called by it the user calls the method directly. For example in Carrano and Savitch [3], the code to print backwards is presented in code segment 5. In their code, two methods were necessary: displayBackward and displayChainBackward. Our approach requires only one method.
D. SEARCH TREE EXAMPLE
This paper demonstrates the power and simplicity of this approach by defining a search tree and deriving a balanced tree from it. A search tree is efficient at finding items if the tree is balanced. However, if the items in the tree are entered in order (rather than randomly) the tree will not be balanced. It will look like the tree in Figure 1. Searching a tree like that is the same as searching a sorted list.
To insure that the tree is efficient for searching, there must be a balancing method. The AVL tree is discussed in a variety of data structures books such as Carrano and Savitch’s book [3, pp. 644-653]. To take advantage of object oriented recursion the code must be modified.
However, an AVL tree can be derived from an object oriented recursive Search Tree with few modifications (only the insert method and a height variable because of the recursion method). Code segment 6 is an implementation of the AVL tree using recursive objects.
Because the recursion is integrated into the object model, only the parts that relate directly to balancing the tree are modified to extend a SearchTree to an AVLTree.
E. RECURSIVE OBJECTS IN C+ +
The recursive object technique was originally developed by the author in C+ + . C++ textbooks also use procedural recursion. For example, Nyhoffs C++: An Introduction to Data Structures [4] introduces recursion with factorial, the Fibonacci sequence and the Towers of Hanoi problem. While Nyhoff tries to avoid recursive presentations even in his tree code, (search and insert is first presented with loops) when a recursive search is presented, it is performed [5] using procedural recursion on a BinNodePointer. While mostly the recursive objects in C++ are designed and built the same as in Java, there is a difficulty in C++’s object model that complicates deriving recursive objects from recursive objects.
A Tree in C++ can access private and protected members of other Trees. If AVLTree is derived from Tree, it can certainly access private and protected members of other AVLTrees. If a Tree has a protected member, e.g. leftSubTree, then an AVLTree can access it. However, it can not access the protected members of Tree that are members of other AVLTrees. Thus an AVLTree can refer to leftSubTree but leftSubTree[arrow right]leftSubTree generates a syntax error because *leftSubTree is a different AVLTree whose Tree members are inaccessible. Even if one puts ((AVLTree *) leftSubTree)[arrow right]leftSubTree a syntax error occurs because an AVLTree is not a Tree. Deriving a recursive type requires either modifying member functions for every data member, or making every data member public.
Java does not require these distortions since its object model actually gives a derived type most of the privileges of the type from which it is derived. The Java model is more natural since, if we derive the student type from the human type, a student should be able to do all the things a human can do, not a highly restricted proscribed list of those things. Since Java was developed much more recently than C+ + , it is to be expected that glitches in C+ +’s object model would be repaired in Java.
F. TEACHING WITH RECURSIVE OBJECTS
The author has successfully applied several methods for teaching recursive objects, most of these being slight modifications of teaching techniques that work on a variety of programming skills.
1. Playlets
One such technique is to have the students actually act out the recursive objects. Each student plays the part of an object, referring to recursively contained objects as necessary. When an operation is applied like a search then the student calls upon other students playing the part of his contained objects until the search is completed. The professor directs these playlets, cueing each performing student as to what his role is in the method and what he must do. The students have learned the materials when they can apply the recursive methods and perform their roles without much cueing or direction.
2. Debugging
Another technique for teaching about recursive objects is to present the students with incomplete or buggy recursive objects code. For example, a traversal method which calls upon the wrong recursive objects or the right objects in the wrong order forces the students to think about what the code should be doing and rewrite it correctly. section G describes the design of this code in detail.
Usually the author presents the code for debugging either in a classroom setting or preferably in a computerized classroom, where students have the code in front of them in their programming environment. Then students can actively struggle with the code compiling changes and seeing how the behavior of the program changes. They can also insert debugging statements in the code to observe how variables change as the code runs. Students need these abilities to complete programming assignments. In these classroom situations, the instructor can advise the students on how to debug the code, what they should be looking for and how to test whether their changes actually fix the code.
3. Illustrations
Drawing illustrations of recursive objects is also highly recommended. Changing an illustration as the code changes the object, creates an animation of what the code does. This is particularly useful for debugging. While the students can not always get five or six friends together to act out a method, they can always find pen and paper and draw a sequence of images of the recursive objects as the method operates. If they are careful, they can detect bugs in buggy code by observing how the animation varies from their intuition of what should be happening in the object.
G. EXAMPLES OF CODE TO DEBUG
The website http://www.matcmp.ncc.edu/~sherd/recursive/ (alternatively in http://polar.ncc.edu/~sherd/recursive/) refers to the code excerpted in this paper. It also refers to code in C+ + and Java used for teaching recursive objects. These programs are crippled, so that the students can practice how to program and debug these objects. The example code is used in a computerized classroom supervised by an instructor. These examples include three methods of involving the students in the coding process.
The first way to involve students with the code is correcting its comments. Generally, the comments to be corrected are questions, which the students replace with answers. Code segment 7 is an example of recursive C+ + code with many such comments. For example, answering the question “why are we using this member to insert?” with the answer “push inserts at position 0” shows that the student actually understands what is happening in the code. Even if the student is told to make this change or guided to make this change by the instructor, it still helps them understand what is happening in the program.
Another way to guide the student is by inserting bugs directly into the program. Code segment 8 is an example of an inserted bug. This code shows the students that they can have all the right lines, but they must be in the right order also. It also helps them to more fully understand traversals. Many bugs whose purpose is to teach students a particular concept are presented in the example code. Some bugs even occurred accidentally and were retained. Note that a comment indicates to the student whether there is an artificially inserted bug in the code (there can be undocumented bugs in code since the code was written by a human).
The final teaching method presented here is leaving lines or even the entire contents of methods from the code. When students fill in missing lines of code and get parts of the program working, they feel the sense of accomplishment that otherwise would require writing an entire program. In the classroom, one can focus on the specific issue being taught and not on tedious coding details. Code segment 9 contains two examples of code with missing lines. Each of these methods requires one new line from the students. The students can only write that line if they understand what the code does.
The pop method requires that the data from the second item in the list be copied to the first, before the second is removed from the list. The top method is marked as a natural bug because it was not intentional, but a real programmer mistake. Since it was an interesting mistake, it was retained in the program but commented as a natural bug. Fixing natural bugs helps improve the morale of the students, by showing even their instructors make simple errors that they (students) can repair.
Sometimes, it is useful to leave out the body of the method and have the students write it from scratch. This gives them some experience in writing significant amounts of code, while not requiring them to write an entire program. Code segment 10 is an example of a method with a missing body from my recursive list code.
H. SUMMARY
This paper presents an approach to teaching recursion that integrates better with object oriented programming. By making each recursion apply to a different object, students can understand recursion better. Many basic data structures can be expressed with recursive objects including lists, trees, and graphs. The paper demonstrates some examples of how one teaches with this code. Generally, using recursive objects is a powerful technique for teaching about one of the more difficult parts of computing.
REFERENCES
1. The Joint Task Force on Computing Curricula, Computing Curriculum 2001 Final Report, Dec. 15 2001, Association for Computing Machinery, IEEE Computer Society.
2. D. S. Malik, P. S. Nair, Data Structures Using Java, Thompson Course Technology, MA, ISBN 0-619-15950-2, pp. 325-326 (2003).
3. F. M. Carrano, W. Savitch, Data Structures and Abstractions Using Java, Prentice Hall, Upper Saddle River, NJ, ISBN 0-13-017489-0 (2003).
4. L. Nyhoff, C++: An Introduction to Data Structures, Prentice Hall, Upper Saddle River, NJ (1999).
5. Ibid, p. 543.
David B. Sher
Department of Mathematics, Statistics, and Computer Processing
Nassau Community College
Garden City, New York 11530
sherd@ncc.edu
Copyright Mathematics and Computer Education Winter 2004
Provided by ProQuest Information and Learning Company. All rights Reserved
