[loxa]

Hello, can someone please explain me this piece of code line by line?

def gen(n):
    # tuple version
    if n == 0:
        yield ()
        return

    for p in gen(n-1):
        yield (1, ) + p
        if p and (len(p)<2 or p[1] > p[0]):
            yield (p[0] + 1, ) + p[1:]

I'm mostly troubled with the statement "yield", and while I've googled for examples, none of them seem to be helping me understand this code as none of them use it in this way.

[Mekire]

Well I can take a stab at explaining this but it isn't easy to follow. This is a generator function; but to make matters worse it is a recursive generator; This means that it is a function that calls itself. And to make matters worse than that, it yields values in three different places.

The yield statements are what makes this a generator. It will return the value it encounters when it hits yield but then it will start in the place it left off when it continues. You can get each value it yields by assigning the function call to a variable and then calling the next() method with the variable as follows:

>>> a = gen(3)
>>> a.next()
(1, 1, 1)
>>> a.next()
(1, 2)
>>> a.next()
(3,)
>>> a.next()
Traceback (most recent call last):
  File "<interactive input>", line 1, in <module>
StopIteration

Notice that once the generator is exhausted it will not yield another value.

It is however more common to iterate over the generator with a for loop (in fact this is done in the generator itself).
If you just want all the values of the generator however you can use:

print(list(gen(integer_here)))

As it is recursive I suggest you start by investigating numbers starting with 0 until you understand what is going on.

For starters try:

>>> print(list(gen(0)))
[()]

as you would expect the initial if clause runs; then yield returns an empty tuple; the function then continues immediately after the yield, and hits a return thus signalling to the generator it is finished.

Now try:

>>> print(list(gen(1)))
[(1,)]

This time the if clause doesn't run because n is not 0. Instead we enter the for loop. The for loop says for p in gen(n-1):. As we just saw, gen(0) is solely an empty tuple, so p is assigned the value (). We then enter the body of the for loop and yield returns the tuple (1,). The code then continues below that yield but as this p evaluates to false, that line doesn't run.

Now I will try to walk you through one last one:

>>> print(list(gen(2)))
[(1, 1), (2,)]

Again the if doesn't run. Go to the for loop. This time (n-1)=1 so the function will call gen(1), which will then as we just saw call gen(0). Eventually gen(1) will return with (1,) and that is the value to which p will be assigned. We now enter the body of the for loop and the yield returns (1,1). Now this time p evaluates to True and the very bottom part of the code runs yielding (2,).


So...... That was pretty ridiculous wasn't it? My first recommendation if you haven't already is to read up on recursion. Write yourself a basic recursive Fibonacci or Factorial number calculator (this isn't efficient, but it is instructive) using regular return statements. Next I recommend you look into some less convoluted generators that use yield statements. After you have a good grasp of both, put them together. Honestly reading code like this is hell no matter what but this will give you the resources to tackle it.

Hope that was somewhat helpful,
-Mek

[baavgai]

This puppy is a mess. I'm not going to try to explain it. However, I do have a way to understand it. Sort of.

You can always ask a program to tell you what it's doing while it executes. For recursive programs, it's usually helpful to have a depth gauge to see how deep into the mess your are.

e.g.

def gen(n, depth=0):
	def trc(*args):
		print('{0} {1} {2}.'.format(depth, '-' * depth, ' '.join(str(a) for a in args)))
	trc("gen(",n,")")
	if n == 0:
		trc("yield ()")
		yield ()
	else:
		for p in gen(n-1, depth + 1):
			trc("p = ", p)
			trc("yield (1, ) + p = ", ((1, ) + p))
			yield (1, ) + p
			if p and (len(p)<2 or p[1] > p[0]):
				trc("p = ", p)
				trc("yield (p[0] + 1, ) + p[1:] = ", ((p[0] + 1, ) + p[1:]))
				yield (p[0] + 1, ) + p[1:]

for result in gen(5):
	print "result =", result

Result:

0  gen( 5 ).
1 - gen( 4 ).
2 -- gen( 3 ).
3 --- gen( 2 ).
4 ---- gen( 1 ).
5 ----- gen( 0 ).
5 ----- yield ().
4 ---- p =  ().
4 ---- yield (1, ) + p =  (1,).
3 --- p =  (1,).
3 --- yield (1, ) + p =  (1, 1).
2 -- p =  (1, 1).
2 -- yield (1, ) + p =  (1, 1, 1).
1 - p =  (1, 1, 1).
1 - yield (1, ) + p =  (1, 1, 1, 1).
0  p =  (1, 1, 1, 1).
0  yield (1, ) + p =  (1, 1, 1, 1, 1).
result = (1, 1, 1, 1, 1)
0  p and (len(p)<2 or p[1] > p[0]) False.
1 - p and (len(p)<2 or p[1] > p[0]) False.
2 -- p and (len(p)<2 or p[1] > p[0]) False.
3 --- p and (len(p)<2 or p[1] > p[0]) True.
3 --- p =  (1,).
3 --- yield (p[0] + 1, ) + p[1:] =  (2,).
2 -- p =  (2,).
2 -- yield (1, ) + p =  (1, 2).
1 - p =  (1, 2).
1 - yield (1, ) + p =  (1, 1, 2).
0  p =  (1, 1, 2).
0  yield (1, ) + p =  (1, 1, 1, 2).
result = (1, 1, 1, 2)
0  p and (len(p)<2 or p[1] > p[0]) False.
1 - p and (len(p)<2 or p[1] > p[0]) True.
1 - p =  (1, 2).
1 - yield (p[0] + 1, ) + p[1:] =  (2, 2).
0  p =  (2, 2).
0  yield (1, ) + p =  (1, 2, 2).
result = (1, 2, 2)
0  p and (len(p)<2 or p[1] > p[0]) False.
2 -- p and (len(p)<2 or p[1] > p[0]) True.
2 -- p =  (2,).
2 -- yield (p[0] + 1, ) + p[1:] =  (3,).
1 - p =  (3,).
1 - yield (1, ) + p =  (1, 3).
0  p =  (1, 3).
0  yield (1, ) + p =  (1, 1, 3).
result = (1, 1, 3)
0  p and (len(p)<2 or p[1] > p[0]) True.
0  p =  (1, 3).
0  yield (p[0] + 1, ) + p[1:] =  (2, 3).
result = (2, 3)
1 - p and (len(p)<2 or p[1] > p[0]) True.
1 - p =  (3,).
1 - yield (p[0] + 1, ) + p[1:] =  (4,).
0  p =  (4,).
0  yield (1, ) + p =  (1, 4).
result = (1, 4)
0  p and (len(p)<2 or p[1] > p[0]) True.
0  p =  (4,).
0  yield (p[0] + 1, ) + p[1:] =  (5,).
result = (5,)
4 ---- p and (len(p)<2 or p[1] > p[0]) ().