Is it a Dell?
I recently came across the same problem on a friend's Dell. The recovery partition was being reported as almost full.
It turned out that - for reasons best known to themselves - Dell had set up the computer to do regular data backups to the recovery partition, so - understandably - after a while the partition filled up.
You might want to see whether this is the case on your computer (Dell or not).