There is provided a recording apparatus which includes a recording medium having a data area with an address assigned to each cluster of a predetermined size; an interface for connection to a host apparatus; writing means for writing data in the data area; access order deciding means for dividing the data area of the recording medium into a plurality of areas each having an optional data capacity, and deciding an order of accessing the divided areas from the writing means; timing deciding means for deciding a timing when file information on written data is to be updated; control means for controlling the writing means to access a plurality of divided areas in accordance with the decided access order, search an empty cluster in the accessed area, and write data in the searched empty cluster and file information updating means for updating the file information on already written data.