# Efficient compilation of linear recursive programs

- Title:
- Efficient compilation of linear recursive programs
- Author:
- Chandra, Ashok K.
- Author (no Collectors):
- Chandra, Ashok K.
- Collector:
- Chandra, Ashok K.
- Description:
- 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.
- Topic:
- Computer science
- Subject:
- Stanford University. Computer Science Department
- Language:
- English
- Physical Description:
- 1 text file
- Publication Info:
- Stanford (Calif.) and cau
- Date:
- April 1, 1972
- Place created:
- Stanford (Calif.)
- Imprint:
- Stanford (Calif.), April 1, 1972
- Genre:
- technical reports
- Identifier:
- CS-TR-1972-282
- Repository:
- Stanford University. Libraries. Department of Special Collections and University Archives
- Collection:
- Stanford Artificial Intelligence Laboratory records, 1963-2009 and Stanford University, Department of Computer Science, Technical Reports
- Manuscript number:
- 3840/2