Properties preserved under recursion removal

Abstract

In this paper we report research which is going on at present. Rather than presenting major results, we have selected a number of partial results and techniques in order to indicate a direction we think is promising. In the first section we review methods for converting a program with a calling structure involving recursion into one without such a structure. In the second section we discuss the separation of the aspects of control and storage in this recursion removal process. We show, by example, how the separation provides the possibility of preserving properties other than functional equivalence. These two sections provide a slight generalization of and complement work presented in the expository paper [S2]. In this third section we illustrate implications of invertibility of operations with respect to the recursion removal process. The central example of this section is the Ackerman functional, obtained by schematizing a version of the Ackerman function. With this example, we note that a recursion need not be convertible to a primitive recursion in order to be removable. © 1972, ACM. All rights reserved.