There and Back Again

Olivier Danvy
Mayer Goldberg

October 2001

Abstract:

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.

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

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.