文章基本信息

标题：There and Back Again
本地全文：下载
作者：Olivier Danvy ; Mayer Goldberg
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2001
卷号：8
期号：39
出版社：Aarhus University
摘要：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.