Swap the first and last characters and recurse.