Recursive

The repeated unnecessary iteration over all variables in $ f$ (during the intersection call in the last section) can be avoided by taking just integers as second argument for the recursive algorithm (in the last section this was intersection).

def recursive_graded(f,d):
    def do_recursive_graded(f,d):
        if f.empty():
            return f
        if d==0:
            if Monomial() in f:
                return Polynomial(1).set()
            else:
                return BooleSet()
        else:
            nav=f.navigation()
            if nav.constant():
                return BooleSet()
            return if_then_else(
                nav.value(),
                do_recursive_graded(BooleSet(nav.thenBranch(),f.ring()),d-1),
                do_recursive_graded(BooleSet(nav.elseBranch(),f.ring()),d))
    return Polynomial(do_recursive_graded(f.set(),d))
Recursive implementations are very compatible with our data structures, so are quite fast. However this implementation does not use any caching techniques. Cudd recursive caching requires functions to have one, two or three parameters, which are of ZDD structure (so no integers). Of course we can encode the degree $ d$ by the d-th Variable in the Polynomial ring.



2009-09-10