This paper proposes a novel frame rate up-conversion (FRUC) algorithm to enhance the motion continuity of video sequences. The proposed algorithm, called the prediction based recursive search (PBRS), can provide a better prediction for frame interpolation. The texture based block partitioning can effectively represent the detailed motions around the object boundaries and thus, the proposed PBRS can find more accurate motions. Thus, the notable image quality improvement can be obtained using PBRS. Experimental results show that the proposed algorithm improves the average PSNR and SSIM of the interpolated frames by up to 2.42 dB and 0.0252, respectively, with relatively low computational complexity compared to the existing algorithms.