Four fours puzzle

Python 155 bytes

h={4:'4',24:'4!',6:'â4',.4:'.4',1:'âû4',4/9.:'.4~'}
f={}
def g(r,s='24',y='4!'):f[eval(s)]=y;[g(r-1,s+o+`k`,y+o+h[k])for k in h for o in'/*-+'if r]
g(3)

The first three bytes (\xEF\xBB\xBF) are the UTF-8 byte order mark, although the file should be saved in an ANSI format. The û and â will be interpretted as √ and Γ respectively in cp437 and cp850, which should work on just about any Windows box.

Runtime is about 0.4s on my computer.

Sample usage (name the file four_fours.py):

$ python
>>> from four_fours import f
>>> f[39]
'4!+4!/.4/4'
>>> f[87]
'4!*4-4/.4~'
>>> for i in range(101): print i, f[i]
0 4!+4!-4!-4!
1 4!+4!/4!-4!
2 4!-4!+Γ4-4
3 4!-4!+4-Γ√4
4 4!+4!/Γ4-4!
.
.
.
96 4!+4!+4!+4!
97 4!*4!/Γ4+Γ√4
98 4!*4+Γ4-4
99 4!*4+4-Γ√4
100 4!*4!/Γ4+4

Results for 0..100. Due to the way the hash is iterated, it prefers to use 4! as often as possible.

Edit: saved a number of bytes by adding Γ√4 = 1, which eliminates the need for any groupings, and by removing √4 = 2, which was no longer necessary.

GolfScript (129 chars*)

[4.`2'√4'24'4!'6'Γ4'1'Γ√4'120'ΓΓ4']2/:F{.F=[[44.`]]*\{`{+{'+*-'1/{:^;.[~@[\]{'()'1/*}%^*@@^~\]\}/}:|~2/~\+|;}+F/}%+}3*\{\0==}+?1=

Running time is on the order of 4 minutes on my PC. A moderate speed-up can be obtained at the cost of two characters by adding a uniqueness operation .& immediately after the %+.

I use pre-coded expressions for 1, 2, 4, 6, 24, 120, and 44, and build the rest up from those using only +, *, and -. This way I don't need to do any non-integer arithmetic in the program itself. I've tried to get simpler expressions by placing the simpler pre-coded values at the start.

All of those values are required^†, and it's necessary to support both directions of subtraction (complex_expression - simple_expression and vice versa). It's also necessary to include some operations which require parentheses (specifically, a*(b-c)), so I bracket all subexpressions indiscriminately.

* I'm counting Unicode code points assuming the program to be UTF-8 encoded, and brushing under the carpet the fact that unless you're using a recent version of Ruby to run the interpreter it's really treating it as ASCII characters. If you're very worried about this, use G for Gamma and v for sqrt.

^† Well, strictly I could remove 44 in exchange for 11 as 44/4 and 71 as √(Γ√4+(ΓΓ4+Γ√4)!), but that's not a good trade-off.

J, 175 161 chars

   f=.')',~'(',;@((<;._2'+ - * % .4 .4~ g(r(4)) r(4) 4 g(4) 4! ( ) '){~(143402 A.i.9)
      /:~(12,11,0,6$0 4 4)+(9$4 7 7)#:((,@(+/,-/,*/,%/)~)^:2,0.4 4r9 1 2 4 6 24)&i.)

   f 1
(.4+.4)+(.4%r(4))

   f 42
(r(4)+4)+(g(4)*g(4))

   f 100
(r(4)+r(4))+(4*4!)

Checked format is (v op v) op (v op v) where v={0.4 4/9 1 2 4 6 24} and op={+ - * /}

full 0..100 results