Programming Forums - Recursion: yield vs. return

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Python (http://www.programmingforums.org/forum43.html)

- - Recursion: yield vs. return (http://www.programmingforums.org/showthread.php?t=10238)

Recursion: yield vs. return

I have been learning Python for a while now. I was browsing old posts in this forum and stumbled across this thread in which Arevos posted the following code:

def permutations(x):

    if len(x) <= 1:

        yield x

    else:

        for i in range(len(x)):

            for p in permutations(x[:i] + x[i + 1:]):

                yield [x[i]] + p

I understand recursion, but what is yield and how does it differ from return? And what is a recursive generator?

Also, I understand the gist of how this function works, but it is more complicated than most recursive functions I have studied. Could someone please explain how this particular function works, especially the last two lines? Thanks.

The yield keyword turns a function into a generator. This allows a function to return more than once, and is typically used in for loops. For example:

def count_to_four():

    yield 1

    yield 2

    yield 3

    yield 4



for number in count_to_four():

    print number

The output when this is executed:

A recursive generator is simply a recursive function that uses yield instead of return.

As for the last two lines, it might make more sense if you understand that:

x[:i] + x[i + 1:]

Is the list x with the ith element removed. And therefore:

permutations(x[:i] + x[i + 1:])

Generates all permutation for the list x without the ith element. Then this line:

yield [x[i]] + p

Adds the ith element back onto the beginning of each permutation. In this way, it recursively generates permutations of the original list.

Thanks, Arevos. I understand it now.

Neat generator example there, Arevos!