|
Article Excerpt
Sometimes, if you do not begin at the end, you end at the beginning. This problem-solving phenomenon, in the realm of computer science (CS), is the subject of this paper. Beginning at the end yields a "working backwards" approach, opposite to that of "working forwards." One might expect 3rd year CS students to be aware of and effectively utilize both approaches. In particular, one might expect that students would work recursively backwards when it is the suitable way for solving a given algorithmic problem. The study in this paper reveals that this is not quite the case. The study shows that a large number of students work solely forwards and obtain erroneous or inefficient results, without considering any redirection of their train of thought. These students' working patterns are characterized and discussed. Suggestions for enabling their awareness and changing the direction of their reasoning are shown and advocated.
**********
Working forwards is the heuristic (way) of approaching a problem by starting from the initial state and advancing forwards, towards the goal state. Working backwards is the heuristic of advancing backwards from the goal state (Polya, 1957). In computer science, the former is a common approach for devising algorithmic problem solutions by incremental, inductive progress, and the latter encapsulates the fundamental notion of recursion.
Algorithmic problems may often be approached in more than one way (Soloway, Spohrer, & Littman, 1989; Linn & Clancy, 1992). Yet, there are problems for which some approaches are more suitable than others. For example, the shortest-path problem in graphs is naturally solved by working forwards, using BFS (Breadth First Search); whereas topological-sort is solved by working backwards, using DFS (Depth First Search). In many optimization and counting tasks, the primary way to gain insight is by reasoning recursively, backwards (Cormen, Leiserson, & Rivest, 1990).
In teaching our students algorithm/program design we would like them to properly invoke and follow suitable solution approaches. In particular, we would like them to invoke a recursive, "working backwards" approach, when it is the suitable way, because recursion is a fundamental problem-solving means in computer science. Do they work backwards when it is the suitable way? The study presented is this paper addresses this question.
Working backwards may require reversing the reasoning direction, from progressing forwards to "undoing" backwards. Such a shift of the train of thought may not necessarily be apparent to all problem solvers. The ability to realize its relevance, and the skill of employing the shift, are primary steps towards recursive thinking. Do students demonstrate such a shift in their way of reasoning during problem solving? Does our teaching yield student awareness of the essential role of reasoning backwards? Or, perhaps not? What can we do to enhance their awareness? These questions have not been addressed in previous studies. The objective of this paper is to shed light on these issues.
The latter questions add a new perspective to previous studies of students in two respects--design considerations and recursive thinking. Previous studies of novice designs typically focused on the construction and composition of program components. Joni & Soloway (1986) have shown that novices devise "working" programs that are poorly constructed and hard to read. Additional studies have shown that novices develop erroneous programs that evolve from inappropriate composition and integration of goals and plans (e.g., Spohrer & Soloway, 1986; Spohrer, Soloway, & Pope, 1989; Ebrahimi, 1994). This study adds the perspective of the "direction" of the generated program plans--forward or backward.
Studies of recursion have mostly focused on difficulties with understanding the recursion concept, the recursion construct, and the recursion process (e.g., Kahney, 1983; Leron, 1988; Segal, 1995; DiCheva & Close, 1996; Levy, 2001). Some studies have also offered animation tools for facilitating the comprehension of recursion (e.g., Wilcocks & Sanders, 1994; George, 2000). In all these studies the students were asked to identify a recursive pattern, devise a recursive program, or analyze a given recursive code. The students were not given a programming task for which they had the choice of devising any solution they wished, be it a direct, "forward" one or a recursive, "backward" one. This study examines whether, upon having to choose by themselves, students select the suitable choice of working backwards, possibly with recursion.
Most of the previous studies on recursion involved students who had just been introduced to the concept and the construct of recursion. This study examines 3rd year CS students who have completed several courses that involve recursion; primarily, CS1, CS2, and Introduction-to-Algorithms. The students gained some experience in devising recursive programs/algorithms, sometimes based on particular recursive design patterns such as tree and graph traversals. Did they develop "working backwards" awareness and competence beyond invoking familiar recursive patterns? This paper shows the student tendencies and offers means for coping with them.
The next section displays the study's methodology, which includes a description of the participants and two unfamiliar algorithmic tasks that were posed to them. The first task was an optimization task, and the second, a...
|
