TY - JOUR AU - Danvy, Olivier AU - Goldberg, Mayer PY - 2001/10/04 Y2 - 2024/03/28 TI - There and Back Again JF - BRICS Report Series JA - BRICS VL - 8 IS - 39 SE - Articles DO - 10.7146/brics.v8i39.21699 UR - https://tidsskrift.dk/brics/article/view/21699 SP - AB - We 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.<br /> <br />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. ER -