This paper discusses a family of algorithms for transforming a recursive program into an equivalent program with a simplified recursion structure. The simplification is performed by integrating copies of certain procedures into the bodies of other procedures. This procedure integration process is analogous to macroexpansion, involving procedure calls rather than macro-operators. We measure the complexity of the recursion structure in terms of the calling graph of the program. This is a directed graph with nodes representing the procedures of the program and arcs representing the relation “calls”. We say that the recursion structure is complex if there is a high degree of cross linkage resulting in a small number of large strongly connected components in the graph; and we say it is simple, if the strongly connected regions are small, preferably containing one node each. One algorithm in our family is optimal in the sense that it finds a program with the same number of procedures and the maximum number of strongly connected regions obtainable via macroexpansion of procedure calls. We discuss suboptimal algorithms which require less running time, and we discuss open problems related to finding simplification algorithms optimal with respect to a wide range of transformations including the inverse of macroexpansion. In particular, we present a very simple open problem concerning the decidability of the word problem for certain semigroups.

This paper proposes the foundations for a systematic study of the translation of recursive function definitions into flow charts (often called the removal of recursions). Several notions of translation are presented. Emphasis is placed on translation which could be performed mechanically, operating only on the syntactical structure of the recursion equations. Systems of recursion equations are classified by structure and by the dynamics of their implicit computations. Theorems on the limitations of translation are based on these classifications. An effective first approximation to a syntactic characterization of one notion of translatability is presented. Finally, open problems are discussed. Space limitations prevent the inclusion of proofs or lengthy definitions.