Recursive function to develop permutations

Alex Martelli aleaxit at
Thu Oct 21 08:33:46 CEST 2004

Steve Goldman <steve_g at> wrote:

> Thanks to everyone for lots to think about.  I really like the concept of
> counting in base "X" as a model for this problem.

You're welcome.

> But now I have another question.  In the elegant recursive generator, below,
> the yield expression for the terminating condition is followed by a return
> statement.  Why is that necessary?  I know it is, because I tried taking it

It's not; a
    raise StopIteration
or putting the rest of the program in an 'else:' would be just as good.

> out with unhappy consequences.   I thought yield had the same effect as
> return, except that the function's state was "frozen" until the next
> iteration.

You need to terminate the recursion sooner or later.  To do that, you
must get a StopIteration exception raised.  That happens with the
appropriate raise statement, or a return, or "falling off the end of the
code", which is equivalent to a return.

I generally prefer return, as it's concise and avoids extra nesting.
But if you'd rather do if/else, you can code, for example:

def permute(Xs, N):
    if N > 0:
        for x in Xs:
            for sub in permute(Xs, N-1):
                yield [x]+sub
        yield []

If you do choose an if/else it seems to me things are more readable when
you arrange them this way (rather than with if N<=0, so the for in the
else).  Matter of tastes, of course.


More information about the Python-list mailing list