# combinations of variable length nested lists

Mark Robinson m.1.robinson at herts.ac.uk
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.

blobby

```