[Tutor] variable numbers of for loops (also iteration/recursion)

[Chris Fuller]

You can always substitute Iteration for Recursion by making the stack an 
explicit part of your code. As an example, imagine you are traversing this 
directory tree:

birds
birds/owls
birds/owls/snowy
birds/owls/barn
birds/owls/great-horned
birds/eagles
birds/eagles/golden
birds/eagles/bald
birds/eagles/osprey

Where the third-level items are files, rather than more directories.

In a recursive approach, a function is defined that does the recursion. This is 
a feature of recursion. You can't slip it inline with your code (unless your 
language supports inline functions and the right sort of scoping rules, but 
you probably don't want to try that here). The function takes a directory, 
iterates through the contents, calling itself again for every subdirectory.

Your application code calls the function with the argument of "birds". The 
function then calls itself twice, once with "owls" and again with "eagles". 
The contents of these are files, and not directories, so recursion ends.

In an iterative approach, there is a stack and a loop. The loop stops when the 
stack is empty. The loop pops the most recently pushed item from the stack, 
and then pushes onto the stack any subdirectories.

We start with the directory "birds" on the stack. The loop pops "birds" and 
then pushes "owls" and "eagles". It loops twice more to process these, and 
then stops.


Your program is really more iterative than recursive. I couldn't manage a 
recursive expression of the problem. You can always make a iterative version 
of a recursive algorithm, but not necessarily the other way. This makes sense 
when you inspect the problem. Your solution is abstractly equivalent to an n-
dimensional "cube" with side length equal to the length of the alphabet, not 
anything that looks like a tree. One thing I noticed about your generated code 
is that it can be collapsed into a list comprehension:

>>> allwrds('ab',2)
listOfWords=[]
for l0 in alphabet:
    for l1 in alphabet:
        word = "".join([eval("l"+str(i)) for i in range(n)])
        listOfWords.append(word)

['aa', 'ab', 'ba', 'bb']

is equivalent to

>>> alphabet='ab'
>>> [l0+l1 for l0 in alphabet for l1 in alphabet]
['aa', 'ab', 'ba', 'bb']

Now, the result is a 1D list of length len(alphabet)**n. Why not iterate over 
that space, and fill in the blanks? Think of your problem modeled as a n-
dimensional hypercube. The value at any element is equal to the concatenation 
of the n indices of that element's location. Some 2D examples:

allwrds('ab',2):
   a   b
a aa  ab
b ba  bb

allwrds('abc',2):
   a   b   c
a aa  ab  ac
b ba  bb  bc
c ca  cb  cc

Mapping from n dimensions to 1D isn't hard if you know the size of each 
dimension. In this case, they're all equal. I'll use a 3D example to make it 
more clear:

i = 0

  j=0  1  2
k
0   0  1  2
1   3  4  5
2   6  7  8

i = 1

  j=0  1  2
k
0   9 10 11
1  12 13 14
2  15 16 17

i = 2

  j=0  1  2
k
0  18 19 20
1  21 22 23
2  24 25 26

Find the i,j,k for 1D index 17.
Start with the highest order index (i). Divide by the product of the sizes of 
the lower dimensions, which is the length of the alphabet squared. This 
alphabet is length 3, so we divide by 9. We get 1 rmdr 8. i=1. Now take the 
remainder and repeat. 8 divided by 3 is 2 rmdr 2. j=2. You could take it 
another step if using n-cubes and powers of the dimension size, since 3**0 
equals one, and the next answer is still 2, but this fails when the dimensions 
aren't all equal. k=2. Got that?

Now these i,j,k values are just indices into the alphabet! Just get the letter 
at that indexd and join them up. Here's the code:

def allwrds(alphabet, n):
   listOfWords=[]
   for i in range(len(alphabet)**n):
      word = ''
      q = i
      for j in range(n-1):
         q, r = divmod(q, len(alphabet))
         word += alphabet[q]
         q = r
      word += alphabet[q]
      listOfWords.append(word)
   return listOfWords


Cheers