recalculate or transform.. depends on how you animate it..
there are very fast algos for generating normals for terrain, and so for deformable terrain recalculation is easy (and you can do "local recalc" instead of recalc everything..)
there is a very fast general algorithm to calc normals wich is O( A+B ) where A is the amount of faces, and B is the amount of vertices..
most the time you don't animate your meshes randomly. if you have keyframes, you can interpolate normals as well (but don't use linear interpolation directly! ..)
if you do skinning, you can transform the normals by the skinning-matrices as well.. you just have to know how to:D
hope that gives some ideas.. i can write down the structure of the algo as well.. isn't it somewhere yet in those forums? ..