Improving Programs by the Introduction of Recursion

A new technique of program transformation,
called "recursion in troduction," is described and 
applied to two algorithms which solve pattern matching problems.
 By using recursion in troduction, algorithms 
which manipulate a stack are first translated into
recursive algorithms in which no stack operations 
occur.  These algorithms are then subjected to a second
transformation, a method of recursion elimination 
called "tabulation," to produce programs with a very
efficient running time.  In particular, it is shown 
how the fast linear pattern matching algorithm of Knuth,
Morris, and Pratt can be derived in a few steps 
from a simple nonlinear stack algorithm.

CACM November, 1977

Bird, R. S.

program transformation, optimization of programs,
recursion elimination, pattern matching algorithms, 
stacks, computational induction

4.0 4.2 5.20 5.24 5.25

CA771113 JB December 27, 1977  6:29 AM

2326	4	2903
2457	4	2903
2842	4	2903
2903	4	2903
2192	5	2903
2903	5	2903
2903	5	2903
2903	5	2903