why can't yield be used in a recursive function

Question

I am using recursion to get the permutation of a list. Here is what I wrote, but the yield version won't work:

def test_permutation_rec():
    print "test 2"
    permutation_rec2([1,2,3],[])     
    print "test 1"
    for one in permutation_rec1([1,2,3],[]):
        print "one:",one 

def permutation_rec1(onelist,prelist):  
    if onelist == [] :
        print prelist
        yield prelist

    lenlist= len(onelist)
    for i, oneitem in enumerate(onelist) :
        leftlist = [onelist[j] for j in range(0,lenlist) if j != i]
        permutation_rec1(leftlist,prelist + [oneitem])

def permutation_rec2(onelist,prelist):
    if onelist == [] :
        print prelist

    lenlist= len(onelist)
    for i, oneitem in enumerate(onelist) :
        leftlist = [onelist[j] for j in range(0,lenlist) if j != i]
        permutation_rec2(leftlist,prelist + [oneitem])

if __name__ == "__main__":
    test_permutation_rec()

the result:

test 2
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
test 1

I think I used yield like in this the answer.

Can anyone tell me why yield doesn't take effect?

By the way, leftlist = [onelist[j] for j in range(0,lenlist) if j != i] in permutation_rec2, is ugly I think. When the list is big, it creates many temporary lists. How can I improve that?

Answer 1

You need to pass on the results of the recursive call; each call returns a generator and you do have to iterate over that. The answer you linked to certainly loops over the recursive call too.

Add a for loop over permutation_rec1() and yield each resulting value on to the next caller:

def permutation_rec1(onelist, prelist):  
    if not onelist:
        yield prelist

    lenlist = len(onelist)
    for i, oneitem in enumerate(onelist):
        leftlist = [onelist[j] for j in range(lenlist) if j != i]
        for res in permutation_rec1(leftlist, prelist + [oneitem]):
            yield res

If you are using Python 3.3 or newer, you can use the new yield from generator delegation syntax:

def permutation_rec1(onelist,prelist):  
    if not onelist:
        yield prelist

    lenlist = len(onelist)
    for i, oneitem in enumerate(onelist):
        leftlist = [onelist[j] for j in range(lenlist) if j != i]
        yield from permutation_rec1(leftlist, prelist + [oneitem])