Removing Redundant Recursion.

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.