[Tutor] cartesian product recursive loop

[Kent Johnson]

Gabriel Farrell wrote:
> In trying to combine a set of lists together, I landed upon
> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/302478 , which
> does the job beautifully.  The problem is I really want to understand
> how it does it, and I can't quite get my brain wrapped around it.
> I'll try to explain, step by step, what I think it's doing, and if
> someone would be so kind as to try to show me where I'm missing
> something, I'd be grateful.
>
> Okay, so here's the function: 
>
> 1   def combine(*seqin):
> 2       def rloop(seqin, listout, comb):
> 3           if seqin:
> 4               for item in seqin[0]:
> 5                   newcomb = comb + [item]
> 6                   rloop(seqin[1:], listout, newcomb)
> 7           else:
> 8               listout.append(comb)
> 9       listout = []
> 10      rloop(seqin, listout, [])
> 11      return listout
>
> We'll start with the example Mr. Klaffenbach gives in the
> documentation on the function: combine((1, 2), (3, 4)) .  Line 10 is
> the first thing to act upon the list of seqin, looking like this:
>
>     rloop(((1, 2), (3, 4)), [], [])
>
> So we go into the rloop function.  There is something left in the
> seqin, so we pass the if statement and hit the for loop.  seqin[0] ==
> (1, 2), and comb == [], so newcomb == [1], the first item, and we're
> sent back into the rloop with the following new setup:
>
>     rloop(((3, 4)), [], [1])
>
> This time around we pass the if statement again and the first item in
> (3, 4) is 3.  comb == [1], so newcomb == [1, 3].  We get sent back to
> the top of the rloop with the following new setup:
>
>     rloop((), [], [1, 3])
>
> Now we fail the if statement, so comb is appended to listout and
> listout == [[1, 3]], which is the first combination to be returned.
>   
So far so good.
> Great.  But, as far as I can see, the whole function should stop right
> here.  How does it produce the rest of the combinations?  I suspect
> I'm misunderstanding something about the for loop, or the way seqin is
> handed into the rloop function.  Any help is much appreciated.
>   
You misunderstand the way recursion works. When the lowest-level call to 
rloop() returns with listout = [[1, 3]], the next level up is still in 
the first iteration of the for loop. The loop continues with comb=[1] 
and item=4. This leads to a call of  rloop((), [[1, 3]], [1, 4]) which 
returns with listout = [[1, 3], [1, 4]]. The for loop at this level 
returns and the loop at the next level up continues.

Each call to rloop() has its own local variables and its own state. 
Returning from one call doesn't pop all the way up the stack, it resumes 
execution at the point of call with the local state restored to what it 
was before the call.

It might help to put in some print statements to help you track the 
flow, or run the program in a debugger and step through it.

Kent