Premium
Eliminating recursion from combinatoric procedures
Author(s) -
Rohl J. S.
Publication year - 1981
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380110804
Subject(s) - recursion (computer science) , sorting , set (abstract data type) , binary number , computer science , mathematics , algebra over a field , theoretical computer science , algorithm , pure mathematics , arithmetic , programming language
The problem of eliminating linear and binary recursion has received quite a deal of attention. Less has been given to the elimination of the more general form of recursion that arises in combinatorics. In this paper we extend earlier work and produce two pairs of equivalent schemata. The correspondences between these schemata and the classical combinatoral problems are given and two applied examples: topological sorting and the set covering problem, are discussed in detail.