Functional languages provide a computational environment where functions are applied to arguments producing results. Once an item is created in memory it is never altered. Function application occurs without side effects. Algorithms involve sequences of function applications (functional composition). Most functional language environments automatically reclaim (garbage collection) items which are no longer needed.
Imperative languages use a state model of computation wherein procedures modify the state of items stored in memory as a computation proceeds from beginning to end.
Functional languages provide somewhat different view of program design which can be useful in the teaching of introductory computer science topics. This paper discusses the use of functional programming techniques in the teaching of recursion and iteration.
The topic of recursion is usually not taught in close combination with iteration in the CS I-CS II course sequence. Sometimes these topics are presented as being unrelated to one another with recursion being treated as a more advanced topic and sometimes less efficient approach to problem solving which should be avoided unless absolutely necessary.
An important problem solving strategy, sometimes called divide and conquer, involves sub-dividing a problem into parts. At least one part, often called a base case, is easily handled and one or more other parts are identical, except smaller, to the original problem. Each of the parts may be handled by the solution or subdivided into parts which may be handled by the solution.
In the following sections, programming examples are given in the Scheme [Har 94,Man 95,Spr 89] and J [Ive 95] programming languages. J is a pure functional language, however, Scheme is not. A subset of Scheme, which omits any Scheme function which mutates an existent Scheme item, is used for the examples in this paper.
The choice of programming language used to teach computer science topics has been widely discussed in the computer science education literature. In particular, [Kon 74,Kon 94,Rie 93,How 94,How 95,How 96,How 97] advocate the use of functional languages, such as J and Scheme, in the teaching of many introductory computer science topics. This paper considers the use of Scheme or J when teaching recursion and iteration.