def print_all(alphabet, n, start_str = ""):
    '''Print all the strings off length n over 
    the alphabet, with start_str at the beginning    
    '''
    #When n is 0, all that we need is just to print start_str
    if n == 0:
        print(start_str)
        return

    for letter in alphabet:
        #if n is 0, this is the same as
        #print(start_str+letter)
        print_all(alphabet, n-1, start_str+letter)

A "top-down" view of why this works:

When n = 0, all that we need to do is print start_str (and then all the strings of length 0, i.e., the empty string). This is exactly what happens.

When n = 1, we need to print start_str, followed by all the possible strings of length 1. For example, if start_str is "zzz", and alphabet is "abc", we need to print "zzza", "zzzb", "zzzc".

This is what happens, since print_all(alpahbet , 0, s) is the same as print(s), so that what happens in print_all for n = 1 is the same as

for letter in alphabet: print(start_str+letter)

When n = 2, we need to print start_str, followed by all the possible strings of length 2. For example, if start_str is "zzz", and alphabet is "abc", we need to print

"zzzaa"
"zzzab"
...
"zzzcc"

That is what happens: We do print_all(alphabet, 1, "zzz"+letter) for every letter So: print_all(alphabet, 1, "zzza") ->print_all(alphabet, 0, "zzzaa") ->print_all(alphabet, 0, "zzzab") ->print_all(alphabet, 0, "zzzac") print_all(alphabet, 1, "zzzb") ->print_all(alphabet, 0, "zzzba") ->print_all(alphabet, 0, "zzzbb") ->print_all(alphabet, 0, "zzzbc") print_all(alphabet, 1, "zzzc") ->print_all(alphabet, 0, "zzzca") ->print_all(alphabet, 0, "zzzcb") ->print_all(alphabet, 0, "zzzcc")

A "bottom-up" view

Say alphabet is "abc"

We start with an empty start_str.

We call print_all as follows in the first call: print_all(alphabet, n-1, "a") print_all(alphabet, n-1, "b") print_all(alphabet, n-1, "c") Like the docstring says, we'll be printing "a" followed by all the possible strings of length n-1, then "b" followed by all the possible strings of length n-1, and so on, so that in the end we'll print all the possible string.

Complexity of print_all

Or we could drawn the call tree

                                                                                 Num calls
   0 0 .... 0 ... 0 ............................................0....0             k^n

       ................................................ 
             .........

      (n-3)..............................................(n-3)                     k^3
        \|||/  \|||/   \|||/    \|||/                 \|||/
         (n-2)(n-2)............(n-2).................(n-2)                         k^2
            \|||/  \|||/    \|||/   \|||/         \|||/
             (n-1) (n-1)   (n-1)   (n-1) ....   (n-1)                              k^1 
                        \|||/  
                         (n)                                                       k^0

For an alphabet of size k, each call spawns k more calls. So on the first level there is 1 call, on the second there are k calls, on the third there are k*k = k^2 calls, on the fourth level there are k*k^2 = k^3 calls, and so on.

On the last level, n = 0, and we start from n, so there are n+1 levels in total. That means that there are k^n calls on the last level, since we started from k^0 on the first level.

Another way to see that on the last level there are k^n calls is to observe that there are as many calls there as there are string printed.

The strings are of length n, and there are k possible choices for each character, which means that are

$$k\times k\times k\times ... \times k = k^n$$

possibilities in total. See e.g. here for details.

In total, we have $1+k+k^2+....+k^n$ calls, which works out to $\frac{1-k^{n+1}}{1-k}$ calls, which is $\mathcal{O}(k^n)$