(Generally, however, they are not classed as polynomial-time algorithms, because the number of objects they generate is exponential.)
Reverse-search algorithms were introduced by David Avis and Komei Fukuda in 1991, for problems of generating the vertices of convex polytopes and the cells of arrangements of hyperplanes.
It finds each objects using a depth-first search in a rooted spanning tree of this state space, described by the following information:[2] From this information it is possible to find the children of any given node in the tree, reversing the links given by the parent subroutine: they are simply the neighbors whose parent is the given node.
Unlike a depth-first search of a graph with cycles, it is not necessary to maintain the set of already-visited nodes to avoid repeated visits; such repetition is not possible in a tree.
However, this recursive algorithm may still require a large amount of memory for its call stack, in cases when the tree is very deep.