Python: how to make a recursive generator function

Question

I have been working on generating all possible submodels for a biological problem. I have a working recursion for generating a big list of all the submodels I want. However, the lists get unmanageably large pretty fast (N=12 is just possible in the example below, N>12 uses too much memory). So I wanted to convert it to a generator function using yield instead, but I'm stuck.

My working recursive function looks like this:

def submodel_list(result, pat, current, maxn):
    ''' result is a list to append to
        pat is the current pattern (starts as empty list)
        current is the current number of the pattern
        maxn is the number of items in the pattern
    '''
    if pat:
        curmax = max(pat)
    else: 
        curmax = 0
    for i in range(current):
        if i-1 <= curmax:
            newpat = pat[:]
            newpat.append(i)
            if current == maxn:
                result.append(newpat)
            else:
                submodel_generator(result, newpat, current+1, maxn)

result = []
submodel_list(result, [], 1, 5)

That gives me the expected list of submodels for my purposes.

Now, I want to get that same list using a recursion. Naively, I thought I could just switch out my result.append() for a yield function, and the rest would work OK. So I tried this:

def submodel_generator(pat, current, maxn):
    '''same as submodel_list but yields instead'''
    if pat:
        curmax = max(pat)
    else: 
        curmax = 0
    for i in range(current):
        print i, current, maxn
        if i-1 <= curmax:
            print curmax

            newpat = pat[:]
            newpat.append(i)
            if current == maxn:
                yield newpat
            else:
                submodel_generator(newpat, current+1, maxn)

b = submodel_generator([], 1, 5)
for model in b: print model

But now I get nothing. A (very dumb) bit of digging tells me the function gets to the final else statement once, then stops - i.e. the recursion no longer works.

Is there a way to turn my first, clunky, list-making function into a nice neat generator function? Is there something silly I've missed here? All help hugely appreciated!

possible duplicate of Python: using a recursive algorithm as a generator — senderle
– senderle, Commented Dec 6, 2011 at 22:29
In Python 3.3 you can use yield from submodel_generator(...). Coming soon... — Dietrich Epp
– Dietrich Epp, Commented Dec 6, 2011 at 22:31
@senderle I agree it's very similar in nature to that post, but unfortunately I'm not good enough at Python to be able to understand what it was that made that one work, so I thought I'd post my similar example anyway, in the hopes of some much needed help! — roblanf
– roblanf, Commented Dec 6, 2011 at 23:07
The cool thing about yield from is that unlike for ... yield it properly handles generator's .send() and .throw() methods. — yak
– yak, Commented Dec 6, 2011 at 23:32

jterrace · Accepted Answer · 2013-04-01 22:33:03Z

27

You should change this:

submodel_generator(newpat, current+1, maxn)

to this:

for b in submodel_generator(newpat, current+1, maxn):
    yield b

This will recursively yield the value from successive calls to the function.

[Update]: Note that as of Python 3.3, you can use the new yield from syntax:

yield from submodel_generator(newpat, current+1, maxn)

edited Apr 1, 2013 at 22:33

answered Dec 6, 2011 at 22:27

jterrace

67.5k24 gold badges164 silver badges208 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python: how to make a recursive generator function

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related