If you have a DVD of whichever OSX you installed, it will run the equivalent of [Command] + R if you boot with the DVD in the drive holding 'c' key down.
Here you can re-establish the recovery partition with disk utility or restore from a Time Machine backup or reinstall from the internet or whatever.