Outputting a 2^n x 2^n matrix
#!/usr/bin/env python

import sys, math

ur = [[1,0],
      [1,1]]

ul = [[0,1],
      [1,1]]

lr = [[1,1],
      [1,0]]

ll = [[1,1],
      [0,1]]


Rather then creating four separate variables, I'd suggest making a list. I'd also suggest using the numpy library for its array type. It makes working with 2D arrays much nicer then using lists of lists.

shapeCounter = 1

matrix = []


Don't use global variables. Instead, pass matrix in as the parameter to the function.

def printMatrix():
    for row in matrix:
        for element in row:
            if(element &gt;= 10):


Parens aren't needed here

                print("%d" % element),
            else:
                print(" %d" % element),
        print
    print


Note that if you used numpy, that library would already be able to nicely print a matrix.

def square(n):
    global matrix


This function should really create and return the matrix

    matrix = [[0]*(2**n) for x in xrange(2**n)]


In numpy, this would be matrix = numpy.zeros( (2**n, 2**n) )

    matrix[0][len(matrix) - 1] = -1
    rec(0, 0, len(matrix) - 1, len(matrix) - 1)
    matrix[0][len(matrix) - 1] = 0
    printMatrix()


Functions that do work on your variables shouldn't print them. Your main control function should do the printing.

def writeRect(rect, x, y):
    global shapeCounter


This isn't a terrible use of a global, but I'd avoid it. I'd have an object this attribute was stored on.

    matrix[y][x] += rect[0][0] * shapeCounter
    matrix[y+1][x] += rect[1][0] * shapeCounter
    matrix[y][x+1] += rect[0][1] * shapeCounter
    matrix[y+1][x+1] += rect[1][1] * shapeCounter
    shapeCounter += 1

def rec(sx, sy, 
        ex, ey):


I wouldn't use abbreviations. Use start_x, end_y to make your code clearer.

    if(ex - sx &lt; 1 or ey - sy &lt; 1):
        return
    #print("(%d,%d) (%d,%d)" %(sx,sy,ex,ey))

    if(matrix[sy][sx] != 0):
        rect = ul
    elif(matrix[ey][sx] != 0):
        rect = ll
    elif(matrix[sy][ex] != 0):
        rect = ur
    elif(matrix[ey][ex] != 0):
        rect = lr


You don't need all those parens

    hx = sx + (ex - sx) / 2
    hy = sy + (ey - sy) / 2

    writeRect(rect, hx, hy)

    rec(sx, sy, hx, hy)
    rec(hx + 1, sy, ex, hy)
    rec(sx, hy + 1, hx, ey)
    rec(hx + 1, hy + 1, ex, ey)

if __name__=='__main__':
    square(int(sys.argv[1]))