Translating recursion equations into flow charts

Abstract

This paper proposes the foundation 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 syntactic structure of the recursion equations. Systems of recursion equations are classified by structure and by the dynamics of their implicit computations. A theorem concerned with the relation between iterative form recursion equations and flow charts completes Part I. In Part II a class of systems of recursion equations which are not translatable is exhibited. A restrictive notion of translatability, motivated by a desire for efficient programs as translations, is characterized for a wide (decidable) class. Translation algorithms are presented. © 1971 Academic Press, Inc.