Accession Number:

ADA058580

Title:

Removing Redundant Recursion.

Descriptive Note:

Technical rept.,

Corporate Author:

CALIFORNIA UNIV SANTA CRUZ INFORMATION SCIENCES

Personal Author(s):

Report Date:

1978-08-01

Pagination or Media Count:

33.0

Abstract:

This paper presents an algorithm that rewrites into efficient form some recursive functions that contain redundant calls e.g. the Fibonacci function. This paper generalizes one method and eliminates the need for the user intervention. Formal definitions are given for the optimization of functions for both linear and multi-dimensional data types. The algorithm depends upon the arguments of the recursive function being defined by a structural induction, and defines a measure of distance on arguments that determines when and how the rewrite can be carried out. This paper is not concerned with the implementation issues arising from the relative efficiency of recursive and iterative mechanisms in programming languages, but rather with restructuring the algorithms themselves.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE