Understanding and Designing Recursive Functions via Syntactic Rewriting

Tom Verhoeff (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)
43 Downloads (Pure)

Samenvatting

Recursion is considered a challenging programming technique by many students. There are two common approaches intended to help students understand recursion. One of them is based on the operational semantics of function execution involving a stack, where students trace the execution of a recursively defined function for some concrete arguments. The other approach is based on the axiomatic semantics involving inductive reasoning with the contract of the recursively defined function. The former approach is not so helpful when designing recursive functions, whereas the latter can be helpful (being a special case of divide and conquer) but con- tracts can be hard to discover.
In this article, I will show a third approach. It is based neither on an operational nor an axiomatic semantics. Rather, it involves a rewriting semantics using program transformation by substitution, thereby inlining function calls. We show that this approach not only may help understanding, but can also be used to design recursive functions.
Originele taal-2Engels
Pagina's (van-tot)99-119
Aantal pagina's21
TijdschriftOlympiads in Informatics
Volume17
DOI's
StatusGepubliceerd - jul. 2023

Financiering

I would like to thank Berry Schoenmakers and Sten Wessel (TU Eindhoven, Netherlands) and Radu Negulescu (Ontario, Canada) for helping me improve this article.

Vingerafdruk

Duik in de onderzoeksthema's van 'Understanding and Designing Recursive Functions via Syntactic Rewriting'. Samen vormen ze een unieke vingerafdruk.

Citeer dit