There and Back Again
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 or , where is unknown, we can detect whether this list is a palindrome in recursive calls and no heap allocation