About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1970
Conference paper
Translating recursion equations into flow charts
Abstract
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 trans-latabillty is presented. Finally, open problems are discussed. Space limitations prevent the inclusion of proofs or lengthy definitions.