Abstract
I show how backtracking can be discovered naturally without using a recursive function (nor using a loop with an explicit stack). Rather, my approach involves a form of self application that can be elegantly expressed in an object-oriented program, and that is reminiscent of how recursion is done in lambda calculus. It also illustrates why reasoning about object-oriented pro- grams can be hard.
| Original language | English |
|---|---|
| Pages (from-to) | 119-132 |
| Number of pages | 14 |
| Journal | Olympiads in Informatics |
| Volume | 15 |
| DOIs | |
| Publication status | Published - 10 Jun 2021 |
| Event | International Olympiad in Informatics (IOI) Conference 2021 - Virtual, Singapore, Singapore Duration: 21 Jun 2021 → 21 Jun 2021 https://ioi2021.sg/ioi-conference/ |
Bibliographical note
T. Verhoeff is Assistant Professor in Computer Science at Eindhoven University of Technology, where he works in the group Software En- gineering & Technology. His research interests are support tools for verified software development and model driven engineering. He re- ceived the IOI Distinguished Service Award at IOI 2007 in Zagreb, Croatia, in particular for his role in setting up and maintaining a web archive of IOI-related material and facilities for communication in the IOI community, and in establishing, developing, chairing, and contrib- uting to the IOI Scientific Committee from 1999 until 2007.Keywords
- computer science
- programming
- object-oriented programming
- functional programming
- backtracking
- recursion
- fixed-point combinator
- self-application
- functional
- self application
- object-oriented