When you say Internet Recovery, did you restart your Mac using the Command+Option+R keys? That's Internet Recovery.
What OS did your Mac come pre-installed with? If it was OS X Snow Leopard or below, you need to boot into your OS X DVD that came with your Mac to reinstall that OS.
If it came pre-installed with OS X Lion, Mountain Lion or Mavericks, you can follow the instructions for each of those in this Apple support link.
You definitely don't want to reinstall OS X Lion or Mountain Lion as those would require the Apple ID/password of the person who purchased those upgrades from the App Store. We all know OS X Mavericks is free, however when selling or giving away a Mac, it's best to put the original OS on it and provide the recipient with the software it came with.
You could contact Apple and ask for the OS DVD that came with it. Just provide the serial number. It would cost you maybe $20, but at least you would have it and could reinstall the original OS.