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.
Paper
Characterizations of flowchartable recursions
Abstract
In this paper we give new characterizations for the flowchartability of recursive functionals. Here flowchart means flowchart with counters (or any arbitrary control structure) and nonflowchartability essentially means requiring access to an unbounded number of data locations during computation of the functional. The general question of flowchartability is recursively undecidable. We present here an effective map from the class of all recursions to a subclass of "representatives" for which the question is decidable. The decision provides a good approximation to a characterization for general flowchartability in the following senses: (1) if a representative is flowchartable, then the recursions it represents are, and (2) there is a straightforward method for flowcharting arbitrary recursions, depending only on recursion structure, such that a recursion is flowchartable by this method if, and only if, its representative is flow-chartable. The main results of the paper are (1) that a representative is flowchartable if, and only if, it is simple or linear, and (2) that, when the context is restricted so that only invertible operations are considered, such a representative is flowchartable if, and only if, it is nested. The terms "simple" and "linear" have been defined in previous papers in the area, although they are extended slightly in this one. The term "nested" is introduced here. Simple, linear, and nested recursions are very easy to identify by inspection. © 1973 Academic Press, Inc.