Recompile allows, among other things, variables to be 'parameter sniffed'. That can be enough to start the optimiser searching in a different area of the plan space, resulting in a different plan.
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass