I currently have a single switch operating a ceiling fan. I'd like to add some recessed lighting to the room. Can I replace the single switch with a double switch to operate the ceiling fan and (4) recessed lights? Or, do I need to install a second switch and run all the wiring?
Possibly. They do make gadgets designed to control a ceiling fan + light separately, using wiring meant for a light only (which is your case even though it's a fan only). They include a control module which goes behind the fan shroud, and an intelligent light switch. The module doesn't care if the fan and light are separate items.
They also make lights designed to depart a ceiling box underneath a fan shroud.
By the way, that setup is currently not code. Code requires every habitable room have a switch at one entry which works a light. If it switches an overhead light, the light must work and not be only a fan. The rule is designed to benefit house guests and first responders.
Speaking of that, not all ceiling boxes are rated to support ceiling fans. There's a big difference both in weight and vibration. So while you're up there, make sure your box is in fact labeled for a ceiling fan. It will say right on it.