Actually the fact that an SP uses the cached plan is one of the oft touted reasons to use SP's rather than dynamic SQL.  It save all that time compiling an execution plan.

I've seen cases where compiling the plan was much longer than the actual execution.  If your SP breaks a task down to where it runs a whole lot of simple querries of dynamic nature the the recompile option might be helpful.