Abstract:Recursion is an important concept in computer science and one that possesses beauty and simplicity, yet many educators describe challenges in teaching the topic. Kim Bruce champions the early use of structural recursion in an object-oriented introductory programming course as a more intuitive concept than traditional (functional) recursion. He uses many graphical examples for motivation (e.g., nested boxes, a ringed bullseye, fractals), providing concreteness to the recursive concept. Internally, most of those examples are disguised forms of a basic recursive list pattern. Recursive lists are important in and of themselves and a mainstay within the functional programming paradigm. However, further challenges exist in providing a tangible presentation for pure lists when disassociated from a graphical structure.
We describe an active-learning exercise in which students play the roles of distinct objects that together comprise the structure of a single, recursive list. This activity establishes intuition that we later use when developing a complete implementation of a recursive list class. Our approach demonstrates a rich set of recursive patterns involving several distinct forms of a base case and varied use of parameters and return values.