A progressive approach to recursion

We propose a progressive approach to simplify teaching recursion. It is introduced by means of three instances of increasing level of difficulty. First, recursion is introduced in a "pure" form as it is found in formal grammars; its accompanying mechanisms are related to rewriting. Later, a functional programming language allows defining recursive functions and recursive data types; its mechanisms are associated to algorithmics and rewriting. Finally, recursion is shown in imperative languages, together with mechanisms about algorithmics and state transformations. The approach has three main advantages. First, the student perceives recursion as a recurrent concept in the discipline of computer science, not only existing in imperative programming. Second, the concept of recursion is isolated and differentiated from other concepts or mechanisms which are associated to particular instances of recursion. Finally, the teaching of recursion is simplified because it is taught in a progressive way.