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(d2(x)),...,f(dn(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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yusuke ICHIKAWA, Zenjiro KONISHI, Yoshihiko FUTAMURA, "Recursion Removal from Recursive Programs with Only One Descent Function" in IEICE TRANSACTIONS on Information,
vol. E88-D, no. 2, pp. 187-196, February 2005, doi: 10.1093/ietisy/e88-d.2.187.
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(d2(x)),...,f(dn(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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.2.187/_p
Copy
@ARTICLE{e88-d_2_187,
author={Yusuke ICHIKAWA, Zenjiro KONISHI, Yoshihiko FUTAMURA, },
journal={IEICE TRANSACTIONS on Information},
title={Recursion Removal from Recursive Programs with Only One Descent Function},
year={2005},
volume={E88-D},
number={2},
pages={187-196},
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(d2(x)),...,f(dn(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.},
keywords={},
doi={10.1093/ietisy/e88-d.2.187},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Recursion Removal from Recursive Programs with Only One Descent Function
T2 - IEICE TRANSACTIONS on Information
SP - 187
EP - 196
AU - Yusuke ICHIKAWA
AU - Zenjiro KONISHI
AU - Yoshihiko FUTAMURA
PY - 2005
DO - 10.1093/ietisy/e88-d.2.187
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2005
AB - 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(d2(x)),...,f(dn(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.
ER -