Teaching object-oriented recursive data structures simplifying the definition and implementation of the data structures

© 2019 Association for Computing Machinery. Recursive solutions to problems are important in teaching computing concepts, particularly in data structures. We can trace linked lists to LISP where their definition is recursive in nature. As we continued to teach these concepts, implementation of such structures gave way to the idea of a node as the simplest part of a linked list. This implementation influenced the way we teach linked lists and we have normally split that into the LinkedList class and the Node class which is typically private. The first solutions the students provide to any processing of the list are typically iterative and not recursive. Even though the definition of a linked list is recursive the solutions we find are not. We present an implementation of a linked list that comes directly from the recursive definition and directs the students to recursive solutions instead of iterative ones. We also present the definition of a binary tree and follow the same principles to help the students think recursively. This approach is language-independent although the code presented is in C#