skip to main content
10.1145/1822090.1822119acmconferencesArticle/Chapter ViewAbstractPublication PagesiticseConference Proceedingsconference-collections
research-article

Tail recursive programming by applying generalization

Published: 26 June 2010 Publication History

Abstract

The design of many tail recursive algorithms can involve thinking about the status of variables and parameters, and how these change with execution flow. In other words, tail recursion is closely related to iteration and imperative programming. However, it is possible to derive tail recursive functions by exclusively using concepts inherent in recursion, such as declarative programming, induction, or problem decomposition. This paper proposes a simple methodology for designing tail recursion functions by using a declarative approach and the concept of function generalization. We have carried out an evaluation of the technique with second and third-year computer science students. Results suggest that this new point of view improves students' ability to design tail recursive programs, helps them understand the distinction between the imperative and declarative paradigms, and may reinforce their programming skills in general. Furthermore, students found the methodology easy to learn and apply, simpler than more sophisticated formal methods, and described it as fast and methodic or mechanical, as it involves a sequence of well-defined steps.

References

[1]
R. M. Burstall and J. Darlington. A transformation system for developing recursive programs. J. ACM, 24(1):44--67, 1977.
[2]
W. Dann, S. Cooper, and R. Pausch. Using visualization to teach novices recursion. SIGCSE Bull., 33(3):109--112, 2001.
[3]
D. Ginat and E. Shifroni. Teaching recursion in a procedural environment -- how much should we emphasize the computing model? SIGCSE Bull., 31(1):127--131, 1999.
[4]
B. Haberman and H. Averbuch. The case of base cases: why are they so difficult to recognize? student difficulties with recursion. SIGCSE Bull., 34(3):84--88, 2002.
[5]
S. M. Haynes. Explaining recursion to the unsophisticated. SIGCSE Bull., 27(3):3--6, 1995.
[6]
C. Pareja-Flores, J. Urquiza-Fuentes, and J. A. Velazquez-Iturbide. WinHIPE: an IDE for functional programming based on rewriting and visualization. SIGPLAN Not., 42(3):14--23, 2007.
[7]
M. Rubio-Sánchez, J. Urquiza-Fuentes, and C. Pareja-Flores. A gentle introduction to mutual recursion. SIGCSE Bull., 40(3):235--239, 2008.
[8]
R. Sooriamurthi. Problems in comprehending recursion and suggested solutions. SIGCSE Bull., 33(3):25--28, 2001.
[9]
J. A. Velazquez-Iturbide. Recursion in gradual steps (is recursion really that difficult?). SIGCSE Bull., 32(1):310--314, 2000.
[10]
C. C. Wu, N. B. D., and L. J. Bethel. Conceptual models and cognitive learning styles in teaching recursion. SIGCSE Bull., 30(1):292--296, 1998.

Cited By

View all
  • (2018)The essence of recursionJournal of Computing Sciences in Colleges10.5555/3204979.320500333:5(115-123)Online publication date: 1-May-2018
  • (2018)Understanding the Effects of Lecturer Intervention on Computer Science Student BehaviourProceedings of the 2017 ITiCSE Conference on Working Group Reports10.1145/3174781.3174787(105-124)Online publication date: 30-Jan-2018
  • (2017)Recursions and how to teach them2017 40th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)10.23919/MIPRO.2017.7973520(740-745)Online publication date: May-2017

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ITiCSE '10: Proceedings of the fifteenth annual conference on Innovation and technology in computer science education
June 2010
344 pages
ISBN:9781605588209
DOI:10.1145/1822090
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

  • Bilkent University: Bilkent University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. design of algorithms
  2. formal methods
  3. generalization
  4. nested recursion
  5. recursion
  6. tail recursion

Qualifiers

  • Research-article

Conference

ITiCSE '10
Sponsor:

Acceptance Rates

Overall Acceptance Rate 552 of 1,613 submissions, 34%

Upcoming Conference

ITiCSE '25
Innovation and Technology in Computer Science Education
June 27 - July 2, 2025
Nijmegen , Netherlands

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)The essence of recursionJournal of Computing Sciences in Colleges10.5555/3204979.320500333:5(115-123)Online publication date: 1-May-2018
  • (2018)Understanding the Effects of Lecturer Intervention on Computer Science Student BehaviourProceedings of the 2017 ITiCSE Conference on Working Group Reports10.1145/3174781.3174787(105-124)Online publication date: 30-Jan-2018
  • (2017)Recursions and how to teach them2017 40th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)10.23919/MIPRO.2017.7973520(740-745)Online publication date: May-2017

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media