Programming Forums > Script Programming > Python

titaniumdecoy · Jun 7th, 2006, 6:37 PM

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:

(Toggle Plain Text)

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.

Arevos · Jun 8th, 2006, 2:57 AM

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:

(Toggle Plain Text)

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:

(Toggle Plain Text)

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:

(Toggle Plain Text)

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

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

(Toggle Plain Text)

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

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

(Toggle Plain Text)

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.

titaniumdecoy · Jun 8th, 2006, 9:48 AM

Thanks, Arevos. I understand it now.

Dietrich · Jun 8th, 2006, 10:52 PM

Neat generator example there, Arevos!

Jun 7th, 2006, 6:37 PM	#1
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 837 Rep Power: 3	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: (Toggle Plain Text) 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 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.

Jun 8th, 2006, 2:57 AM	#2
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 4	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: (Toggle Plain Text) def count_to_four(): yield 1 yield 2 yield 3 yield 4 for number in count_to_four(): print number 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: (Toggle Plain Text) 1 2 3 4 1 2 3 4 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: (Toggle Plain Text) x[:i] + x[i + 1:] x[:i] + x[i + 1:] Is the list x with the ith element removed. And therefore: (Toggle Plain Text) permutations(x[:i] + x[i + 1:]) permutations(x[:i] + x[i + 1:]) Generates all permutation for the list x without the ith element. Then this line: (Toggle Plain Text) yield [x[i]] + p 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.

Jun 8th, 2006, 10:52 PM	#4
Dietrich Professional Programmer Join Date: Feb 2005 Posts: 434 Rep Power: 4	Neat generator example there, Arevos! __________________ I looked it up on the Intergnats!

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Jun 8th, 2006, 9:48 AM	#3
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 837 Rep Power: 3	Thanks, Arevos. I understand it now.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Script Programming > Python

Recursion: yield vs. return