Efficient Compilation of Linear Recursive Programs
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 doesnt 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 sup1 epsilon for arbitratily small epsilon. The author also describes an algorithm that lies between these two it takes time n.logn and space logn. 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.
- Computer Programming and Software