On the Conversion of Indirect to Direct Recursion

Abstract:

Procedure inlining can be used to convert mutual recursion to direct recursion. We present a set of conditions under which inlining can transform all mutual recursion to direct recursion. This will result in fewer procedure calls, and will allow use of optimization techniques that are most easily applied to directly recursive procedures. Conditions are also provided which answer the question, ``when can mutual recursion elimination not terminate?". Also, a technique is presented to eliminate a mutually recursive circuit if it consists of only tail calls.

Bibtex Entry:

@article{KPR:LOPLAS93,
author = {Owen Kaser and  Shaunak Pawagi and  C. R. Ramakrishnan},
title = {On the Conversion of Indirect to Direct Recursion},
journal = {ACM Letters on Programming Languages and Systems ({LOPLAS})},
volume = {2},
number = {1--4},
pages = {151--164},
year = {1993}
}

Full Paper:

[pdf]

C. R. Ramakrishnan
(cram@cs.sunysb.edu)