Recursion and Generators

[Thomas Philips]

I'm teaching myself Python and never having used recursion and
generators, created the simple recursive program shown below and
single stepped through it in IDLE with the debugger turned on to get a
feel for how recursion and generators worked.

def testRecursion(n):
if n == 1:
yield [1]
else:
for result in testRecursion(n-1):
yield result + [n]

print list(testRecursion(4))

As I expect, the program keeps calling testRecursion recursively, and
then backs its way up, yielding a new result each time it exits. All
well and good so far.

However, it then calls testRecursion recursively a second time (see
the sequence of calls below), and of course no results are yielded
this time around.

I'm not sure why it does so. Is it trying to force each genererator to
"drop off the end" and return a StopIteration? If so, should it not
discover that it is done with a level as soon as it backs up to the
next higher level?


'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 2: if n == 1:
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 2: if n == 1:
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 2: if n == 1:
'__main__'.testRecursion(), line 3: yield[1]
'__main__'.testRecursion(), line 3: yield result + [n]
'__main__'.testRecursion(), line 3: yield result + [n]
'__main__'.testRecursion(), line 3: yield result + [n]
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):


Sincerely

Thomas Philips

 

[Terry Reedy]

I'm teaching myself Python and never having used recursion and
generators, created the simple recursive program shown below and
single stepped through it in IDLE with the debugger turned on to get a
feel for how recursion and generators worked.

Bold project. I learned each separately. The two together are sometimes a
challenge to understand.

def testRecursion(n):
if n == 1:
yield [1]
else:
for result in testRecursion(n-1):
yield result + [n]

print list(testRecursion(4))

As I expect, the program keeps calling testRecursion recursively, and
then backs its way up, yielding a new result each time it exits. All
well and good so far.

However, it then calls testRecursion recursively a second time (see
the sequence of calls below), and of course no results are yielded
this time around.

I'm not sure why it does so. Is it trying to force each genererator to
"drop off the end" and return a StopIteration? If so, should it not
discover that it is done with a level as soon as it backs up to the
next higher level?


'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 2: if n == 1:
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 2: if n == 1:
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 2: if n == 1:
'__main__'.testRecursion(), line 3: yield[1]
'__main__'.testRecursion(), line 3: yield result + [n]
'__main__'.testRecursion(), line 3: yield result + [n]
'__main__'.testRecursion(), line 3: yield result + [n]
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):
'__main__'.testRecursion(), line 5: for result in testRecursion(n-1):

Since the yield result line is line 6, not 3, and definitely after rather
than before the line 5 for loop, I do not understand this output. Can you
clarify?

Terry J. Reedy

 

[Thomas Philips]

Terry,

My mistake: I typed the lines as I could not copy them from IDLE's
debug window. All yields other than the first one should indeed be
line 6.

Thomas

 

[Paramjit Oberoi]

def testRecursion(n):

if n == 1:
yield [1]
else:
for result in testRecursion(n-1):
yield result + [n]

print list(testRecursion(4))

Is this what you were trying to do?
.... if n==1:
.... yield 1
.... else:
.... for x in testRecursion(n-1): yield x
.... yield n
....

list(testRecursion(1)) [1]
list(testRecursion(2)) [1, 2]
list(testRecursion(3)) [1, 2, 3]
list(testRecursion(4))

[1, 2, 3, 4]

The generator should yield individual values one after
another, unlike a list of all values like in your example.

HTH,
-param