I like Pythagorean trees

CFDG, 134 characters

This one isn't exactly valid, because you cannot limit the recursion depth. But the problem just calls for a solution in this one. :)

startshape t
c(q)=cos(q/2)^2
d(q)=1+sin(q)/2
p=acos(-1)
shape t{w=rand(p)
SQUARE[x .5 .5]t[trans 0 1 c(w) d(w)]t[trans c(w) d(w) 1 1]}

The results look something like this

For another 46 characters (180 characters in total), you can even colour it in:

startshape t
c(q)=cos(q/2)^2
d(q)=1+sin(q)/2
p=acos(-1)
shape t{w=rand(p)
SQUARE[x .5 .5 h 25 sat 1 b .2]t[trans 0 1 c(w) d(w) b .08 .8 h 2.2]t[trans c(w) d(w) 1 1 b .08 .8 h 2.2]}

Mathematica, 246 234 221 characters

g[n_,s_:1]:={p=RandomReal[q=Pi/2],r=##~Rotate~(o={0,0})&,t=Translate}~With~If[n<0,{},Join[#~t~{0,s}&/@(#~r~p&)/@g[n-1,s*Cos@p],t[#,s{Cos@p^2,1+Sin[2p]/2}]&/@(r[#,p-q]&)/@g[n-1,s*Sin@p],{Rectangle[o,o+s]}]]
f=Graphics@g@#&

This is certainly not the most elegant/shortest way to do this.

Usage: f[8]

And here are example outputs for f[6] and f[10] respectively.

Somewhat ungolfed:

g[n_, s_:1] := With[{p},
  r = Rotate;
  t = Translate;
  p = RandomReal[q = Pi/2];
  If[n < 0, {},
   Join[
    (t[#, {0, s}] &) /@ (r[#, p, {0, 0}] &) /@ g[n - 1, s*Cos[p]],
    (t[#, s {Cos[p]^2, 1 + Sin[2 p]/2}] &) /@ (r[#, p - q, {0, 0}] &) /@
       g[n - 1, s*Sin[p]],
    {Rectangle[{0, 0}, {s, s}]}
    ]
   ]
  ]
f = Graphics@g[#] &

Coffeescript 377B 352B

I feel dirty writing coffeescript but I can't find a decent drawing package for python3 :-/

Q=(n)->X=(D=document).body.appendChild(C=D.createElement('Canvas')).getContext('2d');C.width=C.height=400;M=Math;T=[[175,400,50,i=0]];S=M.sin;C=M.cos;while [x,y,l,a]=T[i++]
 X.save();X.translate x,y;X.rotate -a;X.fillRect 0,-l,l,l;X.restore();T.push [e=x-l*S(a),f=y-l*C(a),g=l*C(b=M.random()*M.PI/2),d=a+b],[e+g*C(d),f-g*S(d),l*S(b),d-M.PI/2] if i<2**n

Javascript 393B 385B

Slightly prettier in javascript and I'm much happier with the for-loop but without the [x,y,z]=A syntax I just can't make it short enough to beat coffeescript

function Q(n){X=(D=document).body.appendChild(C=D.createElement('Canvas')).getContext('2d');C.width=C.height=600;M=Math;T=[[275,400,50,i=0]];while(A=T[i++]){X.save();X.translate(x=A[0],y=A[1]);X.rotate(-(a=A[3]));X.fillRect(0,-(l=A[2]),l,l);X.restore();S=M.sin;C=M.cos;i<M.pow(2,n)&&T.push([e=x-l*S(a),f=y-l*C(a),g=l*C(b=M.random()*M.PI/2),d=a+b],[e+g*C(d),f-g*S(d),l*S(b),d-M.PI/2])}}

Got to say I'm a bit galled this is almost twice as long as the mathematica solution :-/ see it in action: http://jsfiddle.net/FK2NX/3/