
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Recursion Removal from Recursive Programs with Only One Descent Function
Yusuke ICHIKAWA Zenjiro KONISHI Yoshihiko FUTAMURA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E88D
No.2
pp.187196 Publication Date: 2005/02/01
Online ISSN:
DOI: 10.1093/ietisy/e88d.2.187
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Fundamentals of Software and Theory of Programs Keyword: program transformation, recursion removal, tupling,
Full Text: PDF(195KB) >>Buy this Article
Summary:
Recursive programs are often easier to read and write than iterative ones, but their execution frequently requires large numbers of procedure calls and stack operations. This causes problems in program optimization related to inline coding and the locality of data references. In addition to these problems, defining programs recursively sometimes leads to repetitive execution of similar computations, causing programs to have exponential time complexity. As a result, recursion removal methods, which transform a given recursive program to an iterative one without using the stack and increasing the amount of computation time, have been studied since the 1970s. In 1998, our group proposed a recursion removal method for a linear recursive program. In this paper, we extend the method to deal with nonlinear recursive programs with one descent function (RPODs), which are programs of the form f(x) = if p(x) then b(x) else a(c(x),f(d(x)),f(d^{2}(x)),...,f(d^{n}(x))). First, we define the cumulative function for an RPOD. Next, based on the new cumulative function, several transformation techniques for RPODs are shown. These include a unified method of deriving logarithmicorder iterative programs or loopfree programs. Finally, the relationships between our method and various tupling strategies are discussed.

