Report Number: CS-TR-72-282
Institution: Stanford University, Department of Computer Science
Title: Efficient compilation of linear recursive programs.
Author: Chandra, Ashok K.
Date: April 1972
Abstract: We consider the class of linear recursive programs. A linear recursive program is a set of procedures where each procedure can make at most one recursive call. The conventional stack implementation of recursion requires time and space both proportional to n, the depth of recursion. It is shown that in order to implement linear recursion so as to execute in time n one doesn't need space proportional to n: $n^\epsilon$ for arbitrarily small $\epsilon$ will do. It is also known that with constant space one can implement linear recursion in time $n^2$. We show that one can do much better: $n^{1+\epsilon}$ for arbitrarily small $\epsilon$. We also describe an algorithm that lies between these two: it takes time n.log(n) and space log(n). It is shown that several problems are closely related to the linear recursion problem, for example, the problem of reversing an input tape given a finite automaton with several one-way heads. By casting all these problems into a canonical form, efficient solutions are obtained simultaneously for all.
http://i.stanford.edu/pub/cstr/reports/cs/tr/72/282/CS-TR-72-282.pdf