Removing Redundant Recursion.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1978
Accession Number
ADA058580

Entities

People

  • Sharon Sickel

Organizations

  • University of California, Santa Cruz

Tags

Communities of Interest

  • Counter IED
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Construction
  • Efficiency
  • Evolutionary Algorithms
  • Heuristic Methods
  • Information Science
  • Intervention
  • Language
  • Mathematics
  • Military Research
  • Optimization
  • Programming Languages
  • Recursive Functions
  • Redundancy
  • Trees (Data Structures)
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computational Linguistics
  • Operations Research