A program recording apparatus has a program information input device, a program recording setting device, a recording device for writing to, or erasing from a recording medium, and a management device. When the program recording setting device sets the recording of a program, the management device predicts whether there is a shortage of vacant space in the recording medium. This is done when the recording device writes the contents of the program to the recording medium by referring to program management information. To provide vacant space in the recording medium, the management device decides programs to be erased according to predetermined criteria which include an erasure possibility set prior to erasure of the programs to be erased.