How does a for loop containing a function work?

Question

So I saw this code. I know what it does but it's main part (the recursion functions in the for-loops) is throwing me off. The code is

    def flip(c): 
        return str(1-int(c))

    def flip_s(s, i):
         t =  s[:i]+flip(s[i])+s[i+1:]
         return t

    def hamming(s, k):
        if k>1:
           c = s[-1]

           if len(s) >= k: 
              s1=[]
              for y in hamming(s[:-1], k):
                  s1.append(y+c)
           else:
              s1=[] 

           s2 = [y+flip(c) for y in hamming(s[:-1], k-1)]

           r = []
           r.extend(s1)
           r.extend(s2)
           return r

        else:
           return [flip_s(s,i) for i in range(len(s))]

    def main():
        print(hamming('0000',2))

    main()

So if we take the first for-loop

    s1=[]
    for y in hamming(s[:-1], k):
        s1.append(y+c)

how would this work? Thanks.

Answer 1

As with any recursive function, one good way to understand what's going on is to perform a dry run:

Calling hamming with s='0000', k=2
    k is > 1
    c = '0'
    len(s) is >= 2
    s1 = []
    Calling hamming with s='000', k=2
        k is > 1
        c = '0'
        len(s) is >= 2
        s1 = []
        Calling hamming with s='00', k=2
            k is > 1
            c = '0'
            len(s) is >= 2
            s1 = []
            Calling hamming with s='0', k=2
                k is > 1
                c = '0'
                len(s) is _not_ >= k
                s1 = []
                Calling hamming with s='', k=1
                    k is _not_ > 1
                    returning []
                s2 = []
                r = []
                returning []
            Calling hamming with s='0', k=1
                k is _not_ > 1
                returning ['1']
            s2 = ['11']
            r = ['11']
            returning ['11']
        s1 = ['110']
        Calling hamming with s='00', k=1
            k is _not_ > 1
            returning ['10', '01']
        s2 = ['101', '011']
        r = ['110', '101', '011']
        returning ['10', '101', '011']
    s1 = ['100', '1010', '0110']
    Calling hamming with s='000', k=1
        k is _not_ > 1
        returning ['1100', '010', '001']
    s2 = ['1001', '0101', '0011']
    returning ['1100', '1010', '0110', '1001', '0101', '0011']
Done

So hamming(s, k) returns a list of binary strings that are Hamming distance k away from s.

Another nice way to break down a recursive function is to add a depth parameter and use it to indent print statements, as below:

def hamming(s, k, depth):
    print ' '*(4*depth) + 'hamming(' + s + ', ' + str(k) + ')'
    if k>1:
       c = s[-1]

       if len(s) >= k:
          s1=[]
          for y in hamming(s[:-1], k, depth+1):
              s1.append(y+c)
       else:
          s1=[]
       s2 = [y+flip(c) for y in hamming(s[:-1], k-1, depth+1)]

       r = []
       r.extend(s1)
       r.extend(s2)
       print ' '*(4*depth) + 'r = ' +str( r)
       return r

    else:
       x = [flip_s(s,i) for i in range(len(s))]
       print ' '*(4*depth) + 'x = ' + str(x)
       return x

This results in output such as this:

>>> hamming('1001', 2, 0)
hamming(1001, 2)
    hamming(100, 2)
        hamming(10, 2)
            hamming(1, 2)
                hamming(, 1)
                x = []
            r = []
            hamming(1, 1)
            x = ['0']
        r = ['01']
        hamming(10, 1)
        x = ['00', '11']
    r = ['010', '001', '111']
    hamming(100, 1)
    x = ['000', '110', '101']
r = ['0101', '0011', '1111', '0000', '1100', '1010']
['0101', '0011', '1111', '0000', '1100', '1010']

Answer 2

hamming is a function that returns a list. So, in your for loop, you're iterating over the list that hamming returns ... adding c to each element of that list and appending the results to s1.