Recursion: Squeezing the Infinite into the Finite
R. P. Mody, Anuradha Laxminarayan, Jayant Kirtane · 2022 IEEE Frontiers in Education Conference (FIE) · 2022
This Innovative Practice Full Paper presents an approach to the teaching of recursion as part of CS education. Recursion is a concept that is generally considered to be hard. Likewise, in the course of mathematics education, induction is problematic, but for the opposite reason: math students are often bewildered by what looks to them suspiciously like a circular definition. So where recursion is hard to comprehend, induction does not motivate. When we see that induction and recursion are two sides of the same coin, it becomes possible to address math and programming as endpoints of one axis, by solving the pedagogy of recursion and induction together.Furthermore, imperative programming (IP) and OOP lose clarity to efficiency, while functional programming (FP) is declarative at the cost of computational intuitions. This oppositional outlook results in a deleterious proliferation of paradigms. Since FP provides the denotational semantics of IP, while IP gives the implementation semantics of FP, it becomes feasible to integrate these by making language questions more reified in one’s presentation. Hence the second axis: FP – IP.We present recursion as a specific instance of our dual-axis, dual-paradigm approach to teaching programming that weaves together multiple facets of programming theory, foundations and pragmatics into a single narrative. While the entire material tends to increase considerably over the usual approach, especially as the material spans across several courses in the curriculum, it turns out considerably more satisfying to the teacher and kinder to the student this way than all other approaches we have tried.Whereas the conventional view of programming pigeonholes recursion as one programming technique among several, we approach it as an ontology that permeates CS. From this vantage point, we have developed a teaching method based on a set of seven principles and their corresponding actionables. So for instance, teaching co-recursion before recursion is an action that emerges from the perspective that it is data that is essentially recursive, while recursive functions are just the computational mirror of such data.We formulate these principles and the corresponding action-ables interspersed with illustrative programming examples.