First, check if their physical footprint still exists. Go to Settings > General > Usage and check the amount of storage available, do you notice that there is a lot of used storage ? You can also check it through iCloud, which might show used memory labeled as Other.
I lost all my pictures and videos after jailbreaking my phone, yet iCloud showed that they are still taking physical memory (labeled as Other - iCloud did not recognise my pics or vids anymore). This means they cannot be viewed via Camera Roll but they are still stored in the phone.
To fix that, download iFunBox ( http://www.i-funbox.com ) and use it to locate and extract the images from the phone (no need for iCloud to access the phone). I managed to extract all my photos from the iphone to an external USB, which accumulated to over 20GB of photos and videos.
Use this method and you should recover your photos and videos with no previous backup. If your phone shows that there is a lot of empty storage, then your photos might have actually been completely removed.