combinations of variable length nested lists

Mark Robinson m.1.robinson at
Wed Aug 8 16:49:23 CEST 2001

David C. Ullrich wrote:

> It's been determined in many examples that if recursion really bothers
> you when you're writing Python it shouldn't. Or at least it's wrong
> to jump to the conclusion that there's anything wrong with it, it
> has often come out to be the best solution or close to it.
> (There's not all that much recursion in the "obvious" 
> recursive approach, if we apply it to a list containing
> n lists there will be only n calls. As opposed to the 
> first way I wrote it: there's a big difference between
> for x in alist[0]:
>   for t in CartesianProduct(alist[1:]):
> and
> tails = CartesianProduct(alist[1:]);
> for x in alost[0]:
>   for t in tails:
> The first version entails hideously many
> recursive calls.)

just to confirm what you are saying there David. When you first posted 
an example of an 'obvious recursive' solution, I had just come up with a 
recursive solution of my own. Being a little worried about the number of 
recursive calls involved, I tested both, and for the same list (I forget 
the dimensions) while mine clocked up a delightful nine thousane odd 
function calls, your example only required 12. I guess recursion is only 
a problem when you think about it in an inefficient way.


More information about the Python-list mailing list