Eliminating Redundant Recursive Calls

Abstract

CallsThe well-known recursive procedures to compute a given element of the Fibonacci series, to compute a binomial coefficient, and to solve the Towers of Hanoi puzzle define redundant computations.An invocation generally leads to many recursive calls with the same argument value.Such a redundant recursive procedure can be transformed into a nonredundant one when the operations appearing in the procedure have certain algebraic properties.The transformed programs avoid redundancy by saving exactly those intermediate results that will be needed again later in the computation.