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.

The memory effect is a myth. The damage caused by recharging NiCad/NiMH batteries before they're depleted comes from being overcharged in crappy rechargers.