Recursion Removal from Recursive Programs with Only One Descent Function

• ICHIKAWA Yusuke

  Graduate School of Science and Engineering, Waseda University

• KONISHI Zenjiro

  Institute for Software Production Technology, Waseda University

• FUTAMURA Yoshihiko

  School of Science and Engineering, Waseda University

Abstract

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 non-linear 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 logarithmic-order iterative programs or loop-free programs. Finally, the relationships between our method and various tupling strategies are discussed.

Journal

• IEICE transactions on information and systems

  IEICE transactions on information and systems 88 (2), 187-196, 2005-02-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• program transformation
• recursion removal
• tupling

Details

• CRID: 1572261552372366336
• NII Article ID: 110003214176
• NII Book ID: AA10826272
• ISSN: 09168532
• Text Lang: en
• Data Source:
  • CiNii Articles