The wedding recessional song is the first song you’ll hear as a married couple, so it should be a romantic choice for the both of you.