From recursion to iteration: what are the optimizations?
Yanhong A. Liu and Scott D. Stoller
Transforming recursion into iteration eliminates the use of stack
frames during program execution. It has been studied extensively.
This paper describes a general and powerful method, based on
incrementalization, for transforming general recursion into
iteration: identify an input increment, derive an incremental
version under the input increment, and form an iterative computation
using the incremental version. Exploiting incrementalization yields
iterative computation in a uniform way and also allows additional
optimizations to be explored cleanly and applied systematically, in
most cases yielding iterative programs that use constant additional
space, reducing additional space usage asymptotically. We summarize
major optimizations, complexity improvements, and performance
measurements. Our analyses and measurements show that some
previously considered ``optimizations'' can actually result in
slower programs.
BiBTeX
PDF
Scott Stoller's Home Page