Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Simplifying a Recursion Structure

IP.com Disclosure Number: IPCOM000079666D
Original Publication Date: 1973-Aug-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 52K

Publishing Venue

IBM

Related People

Rosen, BK: AUTHOR [+2]

Abstract

In the method described herein, given a recursive program with N procedures, there is constructed a directed graph termed the "calling graph" with a node corresponding to each procedure and arcs representing the relation "calls". The method then applies a variant of "topsort" (as disclosed in Knuth, "The Art of Computer Programming", Vol. 1, pp. 259-265) to the graph, while simultaneously choosing a set * of nodes which cuts all cycles of the graph, and linearizing the partial order provided by the graph with arcs into the set * of nodes deleted.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Simplifying a Recursion Structure

In the method described herein, given a recursive program with N procedures, there is constructed a directed graph termed the "calling graph" with a node corresponding to each procedure and arcs representing the relation "calls". The method then applies a variant of "topsort" (as disclosed in Knuth, "The Art of Computer Programming", Vol. 1, pp. 259-265) to the graph, while simultaneously choosing a set * of nodes which cuts all cycles of the graph, and linearizing the partial order provided by the graph with arcs into the set * of nodes deleted. The linearization then governs the application of the Maggiolo-Schettini & Strong algorithm (as disclosed in the report RC 4069 "A Graph-Theoretic Algorithm with Applications for Transforming Recursive Programs (Preliminary Version)", October 6, 1972, published by the IBM Corporation,) for transforming the program into an equivalent one, whose corresponding graph has a maximum number of strongly connected components. Each component is thus a single procedure or a small set of mutually recursive procedures, which are not involved in recursion with Procedures outside the component.

To attain such maximum number of components, a set * of nodes must have minimal cardinality. In Fig. 1, there is shown a flow chart of the algorithm. This algorithm with block I produces a large, however not necessarily maximal number of strongly connected components. On Fig. 2, there is shown a block I' which can be employed to substitute for block I in the flow chart of Fig. 1. The effect of this substitution is to accomplish the obtaining of the hereinabove mentioned maximum number of components. It is to be realized that all algorithms for accomplishing the obtaining of a strictly minimal set * of nodes in block 1' have worst case times, which are exponential in the number of nodes in the calling graph. Thus, the substitution of block I' (Fig. 2) for block I in the flow chart of F...