ADVANCED TIP FOR THE TECHNICALLY INCLINED: Assuming you didn't jump right in like me and delete your recovery partition on a Windows RT device (haven't tested this on an OEM Windows 8 or Windows 8 Pro machine - yet here's the official guidance - http://technet.microsoft.com/en-us/library/hh825221.aspx), you'll definitely want to at a minimum make the USB Recovery media. I jumped right in and started messing around with my surface and because I backed up the RecoveryImage directory, I was able to recreate my recovery partition. Here are the steps I used and tested on my personal Surface.
So some guy on the Internet told you to delete the recovery partition to regain 3.5 gb of space on your surface - and you did it? Hopefully you followed all my advise and backed up the files on the recovery partition (and created a USB recovery drive as well). To recreate what I just deleted and extended, you go into Computer Management, click on Disk Management and then right click on the Windows (C:) partition and click Shrink Volume.
It will determine how much space is available to shrink. You will shrink it by 3600.
type in 3600 and click Shrink
now you have successfully regained space to create a partition and place the recovery files back on the device.
I created a new simple Volume with the 3600 mb of space, assigned it drive R: (for recovery) and formatted it as FAT32.
You then have a drive to copy the RecoveryImage folder and files into - copy the files and then you can remove the drive letter if you wish.
In disk management, right click on the R: drive partition, change drive letter and paths, and remove the R: (this keeps the partition, but hides it so that files aren't inadvertently deleted, etc.)