Problems in comprehending recursion and suggested solutions

ABSTRACT

Recursion is a very powerful and useful problem solving strategy. But, along with pointers and dynamic data structures, many beginning programmers consider recursion to be a difficult concept to master. This paper reports on a study of upper-division undergraduate students on their difficulty in comprehending the ideas behind recursion. Three issues emerged as the points of difficulty for the students: (1) insufficient exposure to declarative thinking in a programming context (2) inadequate appreciation of the concept of functional abstraction (3) lack of a proper methodology to express a recursive solution. The paper concludes with a discussion of our approach to teaching recursion, which addresses these issues. Classroom experience indicates this approach effectively aids students' comprehension of recursion.

REFERENCES

• 1: Harold Abelson , Gerald J. Sussman, Structure and Interpretation of Computer Programs, MIT Press, Cambridge, MA, 1996
• 2: Adams, J.L. Conceptual Blockbusting: a guide to better ideas (3 ro ed). Addison-Wesley, 1986.
• 3: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 4: David Ginat , Eyal Shifroni, Teaching recursion in a procedural environment—how much should we emphasize the computing model?, The proceedings of the thirtieth SIGCSE technical symposium on Computer science education, p.127-131, March 24-28, 1999, New Orleans, Louisiana, United States
• 5: Kelsey, R., Clinger, W., and Rees, J., et al. The revised 5 report on the algorithmic language Scheme. http://www-swiss.al.mit edu/~jaffer/r5rs_toc.html
• 6: Harry R. Lewis , Larry Denenberg, Data Structures and Their Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: Raja Sooriamurthi, Using recursion as a tool to reinforce functional abstraction (poster session), Proceedings of the 5th annual SIGCSE/SIGCUE ITiCSEconference on Innovation and technology in computer science education, p.194, July 11-13, 2000, Helsinki, Finland
• 8: Polya, G. How to solve it: A new aspect of mathematical method (2nded). Princeton University Press, 1957.
• 9: George Springer , Daniel P. Friedman, Scheme and the art of programming, MIT Press, Cambridge, MA, 1989
• 10: Cheng-Chih Wu , Nell B. Dale , Lowell J. Bethel, Conceptual models and cognitive learning styles in teaching recursion, Proceedings of the twenty-ninth SIGCSE technical symposium on Computer science education, p.292-296, February 26-March 01, 1998, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Documentation, Management