charging rechargeable batteries

is it better to wait until batteries are depleted fully, and then recharging, OR is it fine to recharge batteries when it's half full or partly full?
i'm referring mostly to laptops, mp3 players, phones and the like. i guess i'm slightly concerned about improper charging.

>>8
As already stated, memory effect is very real for NiCd and not a problem for NiMH.  It can often be reversed, and bad chargers might make problem worse, but to claim that overcharging is to blame isn't right.

If you have experience with smart chargers not killing your NiCd batteries when you forget to discharge them fully first, you might be benefitting from the fact that some chargers have a full discharge mode specifically to avoid/fix memory effect on NiCd.