I agree that this is a bad way to learn recursion, but here's a few ideas :
I think you'll have to pass a length into the sort function that's separate from the list length. That way you can turn the outer loop into a recursive call to your function, passing size - 1 each time.
If your homework requires that you use the exact prototypes given, you'll have to play games with only passing the unsorted beginning elements of the vector into each subsequent recursive call and then pushing back the sorted elements as you return from each recursive call.
As others have said, this isn't the most straightforward way of learning about recursion.