[Python] An explanation for the behavior of a basic tree-recursive generator

I am working Q3 in discussion 6 of UCB CS61A. It asks us to implement a tree recursive generator. The answer goes like the following:

def partition_gen(n, m):
"""Yield the partitions of n using parts up to size m.

>>> for partition in sorted(partition_gen(6, 4)):
... print(partition)
1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 2
1 + 1 + 1 + 3
1 + 1 + 2 + 2
1 + 1 + 4
1 + 2 + 3
2 + 2 + 2
2 + 4
3 + 3
"""
if n == m:
yield str(n)
if n - m > 0:
for p in partition_gen(n - m, m):
yield p + ' + ' + str(m)
if m > 1:
yield from partition_gen(n, m-1)


Anyone tries the A=partition_gen(6,4) and call three next(A) would get "2+4","1+1+4" and "3+3" in turn. It would be helpful if somebody could explain to me the logic flow behind this.

That the first next(A) returns "2+4" is obvious. A sequence of recursive calls partiton_gen(2,4),partition_gen(2,3),partition_gen(2,2) is made and finally reaches a base case n=m. Nothing needs explanation here.

A question arises for the next iteration. The program should start where it stops the last time, and make a sequence of recursive calls again: partition_gen(2,4),partition_gen(2,3),partition_gen(2,2). In my understanding, here partition_gen(2,2) is a new call and should generate a new generator. Thus, the program should yield a "2" again here. But for some reason, the program behaves as if this is just another call on the same generator and returns "1+1". However, if we interpret everything this way, then why in the third next(A), when partition_gen(2,2) is called again, no StopIteration error arises?

Besides, it would be quite helpful if somebody could tell me the correct way of thinking about a tree recursive generator. For designing a recursive function, I could wishfully think that the function returns what I want for a smaller size problem, and make sure my program would return the correct thing for a larger problem. But for a recursive generator, it seems that I many extra efforts are needed to carefully keep track of each recursive call and monitor what would be yield for each call. I guess this extra effort can be avoided.

I believe this question must be simple for many of you. Given that I am relatively new to CS, please to patient with me and provide some help.

Continue reading...