Efficient Compilation of Linear Recursive Programs
Abstract
The author considers 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 sup epsilon) for arbitrarily small epsilon will do. It is also known that with constant space one can implement linear recursion in time (n sup 2). The author shows that one can do much better: (n sup(1 + epsilon) for arbitratily small epsilon. The author also describes 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1972
- Accession Number
- AD0747254
Entities
People
- Ashok K. Chandra
Organizations
- Stanford University