Recursion Removal under Environments with Cache and Garbage Collection

Basis of software development is to guarantee productivity and safety. Programming using recursion $\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r} $ garbage collection $(\mathrm{G}\mathrm{C}) $ satisfies these basis, with sacrificing execution time. Recursion removal, which transforms recursive programs into iterative ones, and improvements toward garbage collection tackle this imbalance of advantages and disadvantages. While garbage collection has researched intensively with showing their effects, this is not the case for recursion removal. This report explains recursion removal $\mathrm{b}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}\Leftrightarrow \mathrm{r}\sigma \mathrm{e}\mathrm{a}\mathrm{t} $ refinement toward recursive programs and also ones running with garbage collection under the current computational environment with cache. In our experiments, recursion-removed programs run at most 9.1 times faster than the original at gcc and 5.7 times faster at Common Lisp.