Misconceptions in Recursion: Diagnostic Teaching

John Close
St Patrick College, Dublin, Ireland
email: jsclose@spd.ie

Darina Dicheva
Faculty of Mathematics and Informatics,
Sofia University, Bulgaria
email: darinad@fmi.uni-sofia.bg

Abstract

The paper describes a diagnostic teaching approach to recursion in Logo. The approach involves a general strategy for teaching recursion and specific teaching tactics for alleviating the misconceptions which underly flawed mental models of the recursive process possessed by particular learners. The erroneous mental models and underlying misconceptions had been identified and described in an earlier study by the two authors. Further research to test the approach is recommended.

Keywords

Recursion, mental models, misconceptions, diagnosis, teaching tactics.

1 Introduction

In discussing techniques and procedures for assessing mental models Royer, Cisero, and Carlo (1993) contend that "... knowing that a learner was working with an incorrect mental model and knowing that the nature of that model would be an important diagnostic could lead to an instructional intervention that was specifically designed to repair the flawed model. ... this would involve the identification of all the flawed models that learners might possess, the development of procedures for uniquely identifying each of the models, and the development of instructional procedures designed to repair the specifically identified flawed model".

This paper represents a follow up to a two-year study of children’s difficulties in learning the concept of recursion based on a theory of "mental models" [Dicheva and Close, 1996]. Previous studies of recursion in SOLO, LISP and Logo had identified two mental models of recursion possessed by learners; the incorrect "Loop" model, possessed mainly by novices, and the "Copies" model possessed mainly by experts. [Kahney, 1984; Bhuiyan, Greer, and McCalla, 1992; Kurland and Pea, 1989; Lee and Lehrer, 1988]. The Dicheva and Close study identified thirteen incorrect models of recursion in the work of forty-three high ability children, aged ten to fourteen years, and discussed the misconceptions which appeared to underpin these models.

The goal of this paper is to build on the results of the mental models study by describing an approach to teaching recursion in Logo, which incorporates a diagnostic phase in which students are grouped on the basis of mental models apparent in their work, and provided with tutorial help specific to their particular incorrect mental models and related misconceptions.

2 The Mental Models Study

2.1 Goals of the study

The goals of the mental models study were (1) to identify and classify the mental models of recursion used by children, and, (2) to identify the misconceptions underlying incorrect mental models and the possible sources of the misconceptions.

2.2 Subjects and procedure

The subjects of study were 43 children, aged 10 to 14 years attending extra-curricular Saturday courses on problem-solving with Logo. The courses formed part of an experimental enrichment programme for high ability children which had been in operation in St. Patrick’s College, Dublin since 1985. The children qualified for the courses by achieving a score at the 95^th percentile or better on the Raven’s Progressive Matrices.. The Logo experience of the children in the study varied from 1 course (25 hours) to 6 courses (150 hours), taken over 3 years, with an average of about 3 courses (75 hours) per child. 16 of the 43 children in the study were female.

The study was carried out in 2 stages over 2 ten-week courses, January-March, 1993 and 1994. There were 29 children in the first course and 30 in the second course. 16 of them took both courses. The children were divided into groups on the basis of their experience and progress with Logo. The courses focused on recursive graphics and list-processing and were taught by the two investigators.

2.3 How recursion was taught

In introducing recursion we used a number of principles and approaches:

• Some prerequisite knowledge was mastered before introducing recursion. This included: flow of control in a procedure; interaction between procedures; local variables and scope of variables; iteration.
• Tail recursion was firstly introduced as a generalisation of iteration in cases where the purpose was to construct working forever procedures.

We used a series of such examples, starting with a procedure which simulates the movement of a satellite around the earth in a circle orbit (move.for.ever), then moving onto triangles.for.ever - drawing triangles at different positions and orientation on the screen, which led to the night sky project - scattering stars of different size and colour all over the night sky. (The latter was one of the favourite projects of the children) The tail recursion forever cycle was completed with the spiral project.

• Immediately after constructing the very first recursive procedure the Copies metaphor was introduced for explaining how Logo would execute a recursive procedure.

We preferred the Copies metaphor to the popular Telescoping model since we found it easier both for explanation and for understanding by the children. For the purpose of explanation, paper copies of the definition of the procedure were used.

• Procedures for drawing recursive patterns were taught by using three different approaches: a problem solving approach, a syntactic approach and an architecture approach.

The problem solving approach consists of decomposing a recursive pattern into two parts one of which is a simpler (smaller) version of the original pattern. Thus:

to draw a pattern
draw the base element
draw a smaller pattern

The syntactic approach consists of teaching a template for recursive procedures:

to procedure_name
a base case
a recursive case

The architecture approach consists of describing how recursion works. As already said we used the Copies metaphor. Here the necessity of terminating the work of a recursive procedure was revealed and correspondingly a stop rule was included in the procedure.

• Embedded recursive patterns were introduced using the same three approaches on nested recursive versions of patterns that had already been coded.

We used the tail recursive tower of squares problem followed naturally by the embedded recursive composition of squares problem.

Here the problem solving approach led to decomposing the pattern into three parts, one of which is a simpler version of the original pattern:

to draw a pattern
draw the base element
draw a smaller pattern
draw the base element

The syntactic approach suggested a template as follows:

to procedure_name
a base case
a recursive case
a base case

The place of the stop rule was again discussed when using the architecture approach.

• Tail recursion as well as embedded recursion were introduced both on graphical and on list processing examples.

We found that the children that understood well and were able to write procedures for drawing tail recursive patterns didn’t have any major difficulties with programming embedded recursive patterns.

2.4 Diagnostic assessment of the children’s mental models

A series of worksheets involving tasks calling for the interpretation or construction of short recursive Logo-procedures was administered to the children during the courses.. The worksheets were designed to obtain "snapshots" of their reasoning about recursion at an early stage in the learning process. All the worksheets were completed over the period of the courses during which the children had been introduced to embedded recursion. The children's written work was discussed with them on an individual basis, by asking them to "think aloud" about the problem. This was done to look at the relationships between their thought processes and their written responses.

After the first assessment and discussions we sorted the incorrect procedures into categories and formulated and named the corresponding models. In subsequent assessments and discussions there was confirmation of some of the earlier categories and some new ones appeared. The few not confirmed were discarded. Next, the misconceptions concerning recursion on which the erroneous models were based were described and possible reasons for their occurrence suggested. These misconceptions had been identified in the process of formulating and describing the mental models.

2.5 Summary of the results of the mental models study

In the conducted study thirteen incorrect mental models were identified in the written responses and explanations of forty-three children to problems involving the interpretation and construction of recursive procedures in graphics and list processing. The incorrect mental models used by the children reflected a variety of misconceptions about the nature of recursion, including five relating to the STOP command, seven relating to the structure of recursive procedures, and four relating to the use of local variables. The origins of these misconceptions appeared to be similar to those identified by previous authors (previous experience confusion, overgeneralization, intentionality, natural language confusion, misapplication of analogy).

3 Applying the outcomes of the study

In order to enable the students to correct their erroneous mental models we should first help them to overcome their misconceptions about the different aspects of recursion. We have analysed reasons for the different misconceptions (MCs) and suggest appropriate teaching tactics and activities (TTs) which would lead to improved understanding and correct mental models of recursion.

3.1 Misconceptions in Interpretation Models

3.1.1 Misconceptions about the role of the STOP command

MC1 STOP stops the execution of an embedded recursive procedure. This misconception can arise from previous experience confusion. Since the children’s first experience of the STOP command is in the context of tail-recursion, where it appears to halt completely the execution of the procedure, they assume it does the same thing in an embedded recursive procedure. Another reason is confusion arising from another misconception (MC4), where the students consider a recursive procedure to be a single object instead of a series of procedure copies and so STOP would stop its execution.

TT1 One way to help the students better understand the flow of control in a recursive procedure is to illustrate the interaction between non-recursive procedures, e.g.

Stress the fact that, after finishing the execution of the subprocedure, the control would be passed to the command which follows the procedure call in the main procedure.

A more complex example involving a second level subprocedure could follow the first example.

A suitable metaphor for use with TT1 is "The Little People " metaphor [B. Harvey, 1985].

TT2 The "Copies" model of recursion, which is a correct model, can be used to illustrate the flow of control in a recursive procedure. For example:

The student should be asked to compare the outcomes of running the two procedures and to identify the similarities and differences.

Suitable metaphors for use with T2 are the "Too Many Bears"story [Ahlberg and Amstutz, 1983] and "The Cat in the Hat Comes Back" story [Dr. Seuss, 1958], both of which have recursive structures.

MC2 STOP stops all currently active procedures. This misconception could follow from the previous one, or it could be a result of natural language confusion where the children use the natural language meaning of STOP, i.e. it halts all procedures (including the main one).

TT1 as in MC1

TT2 as in MC1

TT3 One way to help the students to overcome natural language confusion is to discuss with them the computer’s ability to understand natural language words and phrases. Ask the students what happens if Logo is asked to draw a square (not yet defined). Logo responds with "I don’t know how to SQUARE". Then ask them to define a SQUARE procedure, i.e. to teach it the meaning of square:

TO SQUARE
REPEAT 4 [FD 50 RT 90]
END

Discuss Logo’s current understanding of a square, i.e. it is restricted to squares of size 50. Compare this to the restricted meaning of STOP, i.e. "stop the current procedure and go back to the calling procedure". Stress that Logo’s understanding of a word is determined by the definition of the procedure whether it is user defined or a primitive.

MC3 The STOP command does not stop the execution of a recursive procedure. It is seen as part of an IF statement which acts as a check (filter) on the input values. This may be due to confusion arising from another misconception (MC5) where the recusive call is seen as a call for executing the head block just once more; the recursive call itself is not executed again.

TT4 as in MC5

3.1.2 Misconceptions about the structure of recursive procedures

MC4 A recursive call is a looping construct similar to Pascal’s WHILE loop. The head-block of the procedure is the loop body. The loop is executed until the STOP command in the stopping rule halts it. This misconception has its origin in children’s experimenting with tail recursion.

TT2 As in MC1

MC5 The recursive call is a call for executing the head-block. Thus it says that the commands of the head-block should be executed just once more; the recursive call itself is not executed again. The head-block is treated as having the status of a procedure. The recursive call is treated as an ordinary procedure call for executing the head-block. Here the students are looking at the recursive procedure as a "WYSIWYG" (What You See Is What You Get) object.

TT4 To overcome this misconception discuss again the structure of a recursive procedure stressing the fact that the recursive call is a call for executing the entire procedure again.

TT2 As in MC1

MC6 The recursive call just evaluates its own input and does "what the procedure is expected to do", i.e. it moves the turtle forward in the case of graphics procedures, or prints the input, in the case of procedures manipulating words and lists. A common reason for this misconception is intentionality, i.e. the tendency to see a program as intentional ‘being’ with the ability to look forward or back in a procedure.

TT5 A suggested approach is to compare the computer with other machines and their lack of intentionality. A supporting activity would be a project such as "In Plain English" [Fitch and Earle, 1993]. In this project the children write procedures to enable the computer to respond appropriately to sentences such as "Will you draw me a red hat" or "I would like a blue boat". In trying each others procedures they realise that computer understanding is entirely restricted to the words that they have defined for it.

3.1.3 Misconceptions about the way local variables operate in recursive procedures

MC7 A Logo program (a set of procedures) can contain only one variable with a given name. This misconception may be based on the belief that Logo "understands" the natural language meaning of the variables’ names such as SIDE, ANGLE, LENGTH, etc whenever and wherever one uses them. Another reason could be a lack of understanding of local variables in procedures generally.

TT5 see MC6.

TT6 Discuss again variables in nonrecursive procedures, e.g.

Have the students compare the three procedures stressing the fact that each procedure has its own (local) variable S, which is stored in the private (local) section of memory allocated to this procedure

MC8 A recursive procedure maintains only one variable with a given name. At each iteration the variable can be assigned a new value specified by the input in the recursive call. This misconception could follow from adopting another misconception (MC7). Another reason may be that some children believe that if Logo calls the same procedure this procedure should use the same variables. This has proved to work in their experimenting with tail recursive procedures.

TT6 as in MC7.

TT2 Discuss again the "Copies" model, emphasizing that each copy of the procedure has its own local variable.

MC9 A procedure call is interpreted as: MAKE command(s) changing the value(s) of the variable(s) involved, and a command for calling the procedure, for example, CIRCLES :R/2 is interpreted as MAKE "R :R/2 CIRCLES :R

TT7 Younger students find it easier to split the recursive call into two separate steps: (1) decide about the size (the value of the variable) and set it, (2) call the procedure to do the job. This will give a correct solution but it is not in the functional Logo style. But it is better to start from what the children expect and understand and then to discuss the better solution.

MC10 Logo remembers the initial value of a variable, for later use in the commands following the recursive call, i.e. in the tail-block. This could result from misapplication of analogy, e.g. the box metaphor for variables may mislead the students, i.e. if more than one thing could be put in a box why not store more than one value in a variable. Another reason could be overgeneralisation. In this case the students tend to treat the head-block of a recursive procedure as a unit having the status of a procedure. Thus, if the student has a correct concept about local variables he/she would imagine that the head-block would have its private variable whose value is changed at each iteration as specified in the recursive call. After leaving the head-block Logo will use the old (initial) value of the variable in the tail-block.

TT8 To overcome the problem with the box metaphor we suggest replacing it with the name-slot metaphor. In this case the slot can only hold one name (value) at a time.

TT2 An approach to dealing with the problem of overgeneralisation is to again discuss the "Copies" model, emphasizing that each copy is a procedure in itself, and has its own private (local) variable.

3.2 Misconceptions in construction models

3.2.1 Misconceptions about the role of the STOP command

MC11 No need for a STOP command as a recursive program will stop the procedure. This may be attrubuted to intentionality, i.e. the computer is seen as an intentional ‘being’ that knows when a procedure must stop.

TT5 as in MC6.

MC12 Head block and tail block need to be stopped separately, so two STOP commands are included. This often results from another misconception confusion, i.e. it occurs as a consequence of adopting MC14 about the way recursion works.

TT2 as in MC1

TT4 as in MC5 see also MC14.

3.2.2 Misconceptions about the structure of recursive procedures

MC13 Implementation of embedded recursive patterns by using tail-recursive

procedures. For example:

TO TWO.SIDE :S TO R.S :S TO L.S :S
R.S :S IF :S > 200 [STOP] IF :S > 200 [STOP]
L.S :S SQ.RIGHT :S SQ.LEFT :S
END R.S :S * 2 L.S :S * 2
END END

TT9 This is not really an error just a conceptually less mature method for solving the problem. The children simply separate the recursive pattern into two parts, each of which could be constructed by a tail-recursive procedure. In order to help the students to define embedded recursive procedures a suggestion is to demonstrate to them the solving of problems in both ways: first using two tail-recursive procedures, and then using an embedded recursive procedure, and ask themto discuss the two solutions.

MC14 Two recursive calls are included. Recursive calls are seen as looping constructs. Each loop constructs a part of the solution design. In this case the students seem to overgeneralise the correct model of flow of control of tail recursive procedures. They see tail recursive procedures as building blocks for more complex recursive procedures. For example:

TO PATTERN :W
IF :W = " [STOP]
PRINT :W
PATTERN :W BL
IF :W = :W [STOP]
PRINT :W
PATTERN :W ?
END

TT4 as in MC5.

TT2 as in MC1. Discuss the difference between looping through a single procedure and executing muiltiple copies of a procedure.

MC15 Program has an "inductive rule" which tells it what to do so no recursive calls are included. The program is seen as intentional ‘being’ with the ability to know what to do, i.e. to know that repetition is required. For example:

TO SQS :S
IF :S < 20 [STOP]
SQUARE :S MOVE :S
SQUARE :S - 20
IF :S < 100 [STOP]
SQUARE :S MOVE :S
SQUARE :S + 20
END

TT5 as in MC6.

MC16 Recursion needs a rule to be specified which tells the computer how to produce a recursive pattern. This rule specifies how to produce the next element of the recursive pattern from the preceding element. This misconception is related to the children’s previous experience in producing similar patterns with nonrecursive procedures. See the example for MC15.

TT10 One way to overcome this misconception is to discuss recursion as a problem solving technique, initially with a simple tail-recursion procedure, for example, a tower of squares reducing in size, and later with an embedded recursion procedure. The key aspect of this approach involves decomposing the pattern into two parts: a simple part (one square) and a similar pattern with the same structure as the initial pattern (a smaller tower of squares). In this way the pattern is not considered as a sequence of elements, i.e. there is not a next element, just one element and the rest of the pattern.

4 Summary

The present paper described a general strategy for teaching recursion in Logo. It also set out specific teaching tactics for alleviating the misconceptions which underly flawed mental models of the recursive process possessed by particular learners. The erroneous mental models had been identified and desribed in an earlier study by the two authors. Further research to test the diagnostic teaching approach is recommended.

References

1. Ahlberg, A. and Amstutz, A.(1983) Ten in a Bed London, Granada
2. Bhuiyan, S. H., Greer, J. E., and McCalla, G. I. (1992) Learning recursion through the use of a mental model based programming environment. In Proceedings of the Second International Conference on Intelligent Tutoring Systems. 50-57, Montreal.
3. Close, J. and Dicheva, D. (1994) Mental Models in Constructing Recursive Procedures. In Proceedings of East-West International Conference on Computer Technologies in Education, Crimea, Ukraine, pp. 48-53.
4. Dicheva, D. (1991) How to Introduce Recursion in Logo, In Proceedings of the Third European Logo Conference, Parma, Italy, pp. 641-650.
5. Dicheva, D. and Close S. (1993) Misconceptions and Mental Models of Recursion, In Proceedings of the Fourth European Logo Conference, Athens, Greece, pp. 12-20.
6. Dicheva, D. and Close J. (1996) Mental Models of Recursion. Journal of Educational Computing Research. Vol. 14 (1), 1-23
7. Dr Seuss (1958) The Cat in the Hat Comes Back, Beginner Book series, New York: Random House.
8. Fitch, D. and Earle, S. (1993) 101 Ideas for Logo, Terrapin Software, Inc.
9. Harvey, B. (1985) Computer Science Logo Style, MIT Press.
10. Kahney, H. (1984) Modelling novice programmer behaviour. In: Yazdani, M. New horizons in educational computing. Ellis Horwood Ltd., 101-118.
11. Kurland, D.M., and Pea, R.D. (1989) Children’s mental models of recursive Logo programs. In: Soloway, E., Spohrer. Studying the novice programmer, LEA, 315-323.
12. Lee, O., and Lehrer, R. (1988) Conjectures concerning the origins of misconceptions in Logo. Journal of Educational Computing Research, 4(1), 87-105.
13. Nikolova, I. (1991) A Metaphor Explaining Scope Rules for Variables in Logo, In Proceedings of the Third European Logo Conference, Parma, Italy, pp. 651-662.
14. Royer, J.M., Cisero, C.A., and Carlo, M.S. (1993) Techniques and Procedures for Assessing Cognitive Skills. Review of Educational Research. Vol. 63 (2) 201-243

BIOGRAPHIES

John (Sean) Close is a senior lecturer in mathematics education and educational computing in St. Patrick’s College, Dublin and Dublin City University, Ireland. His research interests include the methodological and cognitive aspects of computer applications in schools. He is chairman of the Irish Logo Users Group, member of the executive council of the Computer Education Society of Ireland, member of the Association for the Advancement of Computers in Education (AACE) and member of the scientific committee of Eurologo. E-mail: jsclose@spd.ie

Darina Dicheva is an associate professor at Faculty of Mathematics and Informatics, University of Sofia. Her research interests include artificial intelligence and education, esp. intelligent tutoring systems and intelligent learning environments, as well as methodological issues of teaching informatics at school. She is a member of: the executive committee of the Central European chapter of AACE (Association for Advancement of Computers in Education), the IFIP WG 3.3 "Research on Educational Applications of Information Technologies", the editorial board of the East-West Journal on Computers and Education, the EUROLOGO International scientific committee, the programme committees of a number of international conferences. URL: http://www-it.fmi.uni-sofia.bg/~darinad/