zbMATH — the first resource for mathematics

Recursion removal/introduction by formal transformation: An aid to program development and program comprehension. (English) Zbl 0956.68014
Summary: The transformation of a recursive program to an iterative equivalent is a fundamental operation in computer science. In the reverse direction, the task of reverse engineering (analyzing a given program in order to determine its specification) can be greatly ameliorated if the program can be re-expressed in a suitable recursive form. However, the existing recursion removal transformations, such as the techniques discussed by D. E. Knuth [\((*)\) Computing Surveys 6, 261-301 (1974; Zbl 0301.68014)] and R. S. Bird [\((**)\) Commun. ACM 20, 434-439 (1977; Zbl 0358.68016)], can only be applied in the reverse direction if the source program happens to match the structure a produced by a particular recursion removal operation. In this paper we describe a much more powerful recursion removal and introduction operation which describes its source and target in the form of an action system (a collection of labels and calls to labels). A simple, mechanical restructuring operation can be applied to a great many iterative programs, which will put them in a suitable form for recursion introduction. Our transformation generates strictly more iterative versions than the standard methods, including those of \((*)\) and \((**)\). With the aid of this theorem we prove a (somewhat counterintuitive) result for programs that contain sequences of two or more recursive calls: under a reasonable commutativity condition, ‘depth-first’ execution is more general than ‘breadth-first’ execution. In ‘depth-first’ execution, the execution of each recursive call is completed, including all sub-calls, before execution of the next call is started. In ‘breadth first’ execution, each recursive call in the sequence is partially executed but any sub-calls are temporarily postponed. This result means that any breadth-first program can be reimplemented as a corresponding depth-first program, but the converse does not hold. We also treat the case of ‘random-first’ execution, where the execution order is implementation dependent. For the more restricted domain of tree searching we show that a ‘breadth-first’ search is the most general form.
We also give two examples of recursion introduction as an aid to formal reverse engineering.

68N01 General topics in the theory of software
Full Text: DOI