The recording apparatus of the present invention: stores therein one or more recorded data pieces, each of which is created by encoding a video data piece, and one or more encoding information sets, each of which is information extracted when a different one of the video data pieces is encoded and represents characteristics of the video data piece; selects a recorded data piece based on the stored encoding information sets; creates a re-encoded data piece by re-encoding the selected recorded data piece using a predetermined encoding method; extracts a corresponding re-encoding information set in a course of creating the re-encoded data piece; and stores (a) the re-encoded data piece which replaces the selected recorded data piece and (b) the re-encoding information set which replaces an encoding information set corresponding to the selected recorded data piece.