CODEWITHSUNDEEP
pythongeneratorrecursion
Lord British
Lord British

Reputation: 425

Python: is it possible to mix generator and a recursive function?

Is there a way to make the something like the following code work?

add = lambda n: (yield n) or add(n+1)

(answers don't need to be in functional style)

Upvotes: 5

Views: 1920

Answers (3)

pillmuncher
pillmuncher

Reputation: 10162

def add(n):
    yield n
    for m in add(n+1):
        yield m

With recursive generators it's easy to build elaborate backtrackers:

def resolve(db, goals, cut_parent=0):
    try:
        head, tail = goals[0], goals[1:]
    except IndexError:
        yield {}
        return
    try:
        predicate = (
            deepcopy(clause)
                for clause in db[head.name]
                    if len(clause) == len(head)
        )
    except KeyError:
        return
    trail = []
    for clause in predicate:
        try:
            unify(head, clause, trail)
            for each in resolve(db, clause.body, cut_parent + 1):
                for each in resolve(db, tail, cut_parent):
                    yield head.subst
        except UnificationFailed:
            continue
        except Cut, cut:
            if cut.parent == cut_parent:
                raise
            break
        finally:
            restore(trail)
    else:
        if is_cut(head):
            raise Cut(cut_parent)

...

for substitutions in resolve(db, query):
    print substitutions

This is a Prolog engine implemented by a recursive generator. db is a dict representing a Prolog database of facts and rules. unify() is the unification function that creates all substitutions for the current goal and appends the changes to the trail, so they can be undone later. restore() does the undoing, and is_cut() tests if the current goal is a '!', so that we can do branch pruning.

Upvotes: 3

Tony Veijalainen
Tony Veijalainen

Reputation: 5555

Your function seems to me just to be other expression for unbound sequence:

n, n+1, n+2,....

def add(x):
    while True:
        yield x
        x+=1

for index in add(5):
    if not index<100: break ## do equivalent of range(5,100)
    print(index)

This is not recursive, but I see no need for recursive style here.

The recursive version based on the other answers link, which had generators calling generators, but not recursively:

from __future__ import generators

def range_from(n):
    yield n
    for i in range_from(n+1):
        yield i

for i in range_from(5):
    if not i<100: break ## until 100 (not including)
    print i

Upvotes: 0

ars
ars

Reputation: 123488

I'm not sure of the intent of "yield(n) or add(n+1)", but recursive generators are certainly possible. You might want to read the link below to get a grip on what's possible, in particular the section titled "Recursive Generators".

Upvotes: 3

Related Questions