Additional information is generated for each of unit recording blocks in a recording medium. The generated additional information is recorded on a first area in the corresponding unit recording block. A piece of file data is recorded on a second area in each of the unit recording blocks. The second area differs from the first area. The additional information for each of the unit recording blocks includes 1) file identification information for identifying the file data, 2) next-sector address information indicating an address of a unit recording block following the present unit recording block, and 3) first-sector identification information indicating whether or not the present unit recording block is first one of the unit recording blocks assigned to the file data. The additional information may further include effective-data identification information indicating whether a piece of the file data recorded on the present unit recording block is effective or ineffective.