[Tutor] recursive generator

[Chris Fuller]

Here's a (more or less) useful example.  It generates the "nth triangular 
series" (my term), n=2 is the triangular numbers, n=3 the tetrahedral numbers 
(n has a correspondence to dimension).  Each series is the sum of the elements 
of the previous one.  They are also the columns of Pascal's Triangle.

Probably only "useful" if you enjoy playing around with math.

def triangular(n):
   if n == 0:
      while True:
         yield 1
   else:
      g = triangular(n-1)
      a = 0
      while True:
         a += g.next()
         yield a


I wouldn't use that to build Pascal's triangle, by the way (usually you want 
it rowwise).  Here's my code.

def pascal():
   r = 0
   l = [1]
   yield l

   while True:
      l  = [1] + [ l[i] + l[i+1] for i in range(r) ] + [1]
      r +=  1

      yield l

>>> g=pascal()
>>> for i in range(9):
...  print ' '.join(['%2d'%(i,) for i in g.next()])
... 
 1
 1  1
 1  2  1
 1  3  3  1
 1  4  6  4  1
 1  5 10 10  5  1
 1  6 15 20 15  6  1
 1  7 21 35 35 21  7  1
 1  8 28 56 70 56 28  8  1

Here are the triangular-ly generated numbers (I made them a square, just to 
illustrate an interesting property.)
>>> for i in range(7):
...  g=triangular(i)
...  print ' '.join(['%3d'%(j,) for j in [g.next() for k in range(7)]])
... 
  1   1   1   1   1   1   1
  1   2   3   4   5   6   7
  1   3   6  10  15  21  28
  1   4  10  20  35  56  84
  1   5  15  35  70 126 210
  1   6  21  56 126 252 462
  1   7  28  84 210 462 924


Cheers

On Sunday 07 March 2010, spir wrote:
> Hello,
> 
> Is it possible at all to have a recursive generator? I think at a iterator
>  for a recursive data structure (here, a trie). The following code does not
>  work: it only yields a single value. Like if child.__iter__() were never
>  called.
> 
>     def __iter__(self):
>         ''' Iteration on (key,value) pairs. '''
>         print '*',
>         if self.holdsEntry:
>             yield (self.key,self.value)
>         for child in self.children:
>             print "<",
>             child.__iter__()
>             print ">",
>         raise StopIteration
> 
> With the debug prints in code above, "for e in t: print e" outputs:
> 
> * ('', 0)
> < > < > < > < > < > < > < > < >
> 
> print len(t.children) # --> 9
> 
> Why is no child.__iter__() executed at all? I imagine this can be caused by
>  the special feature of a generator recording current execution point. (But
>  then, is it at all possible to have a call in a generator? Or does the
>  issue only appear whan the callee is a generator itself?) Else, the must
>  be an obvious error in my code.
> 
> 
> Denis
>