This is how I would write it:

 sneakydeterminant[m_] := sneakydeterminant[m] = 
 sneakydeterminant[Transpose[m]] = Module[{answer},
 If[Length[m] == 1,
 m[[1, 1]]],
 Sum[Power[-1, j + 1] m[[1, j]] sneakydeterminant[
 m[[Complement[Range[Length[m]], {1}], 
 Complement[Range[Length[m]], {j}]]]], {j, 1, Length[m]}]
 ]
 ];

The only difference is the time at which the new DownValue is added, but it should be equally safe.