The present invention relates to a recording apparatus and a method, a playback apparatus and a method, a recording medium, and a program capable of quickly playing back a picture associated with a unit in which a moving image is encoded. An extraction section 51 extracts one picture from each GOP. A number-of-pixels conversion section 40 reduces the amount of information of the extracted picture by thinning out pixels. A static-image compression section 41 encodes the picture whose amount of information has been reduced by a JPEG technique. A microcomputer 31 associates the encoded picture with the GOP from which the picture has been extracted and controls recording of the picture associated with the GOP onto a disk 45 on which the moving image is to be recorded. The present invention can be applied to a recording apparatus for recording a moving image onto a data recording medium.