Notes on recursion elimination

ABSTRACT

Various methods of recursion elimination are applied to the schematic recursive procedure: proc S(x); px then N(x); S(ƒx); S(gx); M(x) fi. Procedures with this general form arise in connection with tree traversal and sorting algorithms. Each method of recursion removal involves the use of one or more stacks, and the solutions are compared on the basis of their running time.

REFERENCES

• 1: Ashok K. Chandra, Efficient compilation of linear recursive programs., Stanford University, Stanford, CA, 1972
• 2: Darlington, J. and Burstall, R.M. A system which automatically improves programs. Proc. 3rd Int. Conf. on Artificial Intelligence, Stanford University, Stanford, Calif., 1973, pp. 479-485.
• 3: Dijkstra, E.W. Recursive programming. Numerische Mathematik 2 (1960), 312-318.
• 4: Hoare, C.A.R. Quicksort. Computer J. 5 (1962), 10-15.
• 5: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 6: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 9: James H. Morris, Jr., Another recursion induction principle, Communications of the ACM, v.14 n.5, p.351-354, May 1971 [doi>10.1145/362588.362598]
• 10: Paterson, M., and Hewitt, C.E. Comparative schematology. In Rec. Proj. MAC Conf. on Concurrent Systems and Parallel Computation, ACM, New York, 1970, pp. 119-128.
• 11: Strong, H.R. Jr., Translating recursion equations into flowcharts. J. Comptr. System Sci. 5 (1971), 254-285.

INDEX TERMS

Keywords:
computational induction, optimization of programs, recursion elimination, sorting algorithms, stacks, trees