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