From recursion to iteration: what are the optimizations

Transforming recursion into iteration eliminates the use of stack frames during program ex-ecution. It has been studied extensively. This paper describes a general and powerful method, based on incrementalization, for transforming general recursion into iteration: identify an in-put increment, derive an incremental version under the input increment, and form an iterative computation using the incremental version. Exploiting incrementalization yields iterative com-putation 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 addition-al 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.