Recursive Convergence

Date
2017
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Haverford users only
Tripod URL
Identifier
Abstract
Ideally, we would always be able to write clear, concise programs and have them run quickly. One major impediment is the redundancy which can occur in direct recursive solutions. In some cases, this means writing a loop even if the programmer is more comfortable thinking in terms of recursion. In other cases the impact on code is even more dramatic, and in these cases most programmers choose to sacrifice clarity in exchange for improved asymptotic complexity. There exist program transformation techniques that would allow us to write idiomatic recursive programs without losing efficiency. One such transformation is the “tupling" transformation, which can and has been implemented as an automatic compiler optimization. This transformation is, however, only applicable to a narrow class of problems. We are exploring related transformations, such as tabulation, which can helpfully be applied to a wider class of recursive programs, and attempting to answer the question of when these transformation techniques are most useful to programmers aiming to balance program clarity with performance.
Description
Subjects
Citation
Collections