There and Back Again
AbstractWe illustrate a variety of programming problems that seemingly require two separate list traversals, but that can be efficiently solved in one recursive descent, without any other auxiliary storage but what can be expected from a control stack. The idea is to perform the second traversal when returning from the first.
This programming technique yields new solutions to traditional problems. For example, given a list of length 2n or 2n+1, where n is unknown, we can detect whether this list is a palindrome in n+1 recursive calls and no heap allocation.
How to Cite
Danvy, O., & Goldberg, M. (2001). There and Back Again. BRICS Report Series, 8(39). https://doi.org/10.7146/brics.v8i39.21699
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.