Recursion and Generators

Justin Azoff justin.azoff at gmail.com
Sat Jul 10 02:08:48 CEST 2004


The problem is that you are yielding a yield... Think of it like: yield
returns a "pointer" to your data, this works the first time. The second
call will yield a value, then as it backs up, it will yield the yielded
value.  Anyway, the way I've found to do this is to either use a thread
with a message queue, seems to work for me at least:

from threading import *
from Queue import Queue, Empty

class MyFunc:
def __iter__(self):
return self

def next(self):
while 1:
n=self.Q.get()
if n==None:
raise StopIteration
else :
return n

def __init__(self,x):
self.Q=Queue()
self.t=Thread(target=self.recfunc,args=(x,))
self.t.start()

#then the actual function:
def recfunc(self,x):
if x==0:
self.Q.put(None) #all done
return
else :
self.Q.put(x) #"yield" it
self.recfunc(x-1)
return


# then you can use it like
for x in MyFunc(10):
print x,

There might be an even simpler way to do this, who knows :-)

Thomas Philips wrote:
> 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




More information about the Python-list mailing list