Basically as I understand it, exposure does pretty much what you would expect, reduces or increases the exposure.
Recovery, however, works differently - if an image appears overexposed, it may be only one or two channels which are blown. Recovery uses the data in the channels which aren't blown to recreate the 'blown' channels.
You can see the difference in the effect by watching the effect in the histogram display while moving the sliders. With exposure you'll notice very significant changes in the midtones, while the effect of recovery is pretty much expected to the highlights.
The best result will depend on exactly what the problem is. Often if the image is correctly exposed with just a few blown highlights, revovery does a good job. If the image is underexposed, then exposure may be the best tool.
But there are lots of different views on this. Some advocate fairly radical use of exposure (eg. up to -1.00) to pull back the highlights then use the brightness control to boost the midtones.
Colin K. Work, Pixstel