iPhone 4 - is it possible to do a photo recovery for photos without a previous backup
Before a sync or restore, I believe that iTunes will create a backup of your phone's contents (unless you manually cancel this backup). The backup will contain the photos and videos that were on the phone.

You can check if a backup was created by doing the following:


Launch iTunes
iTunes > Preferences > Devices
See if there is an entry with the date of the restore.


If a backup exists, you can recover your data with one of two methods:


Restore your phone using that backup; or
Use an application such as iPhone Backup Extractor to extract the images out of the backup file.