Abstract. In conventional fractal image coding (FIC) schemes, domain blocks are constrained to be twice as large as range blocks to ensure the convergence of their iterative decoding stage. However, this constraint has limited the fractal encoder to exploit the self-similarity at the same resolution scale of natural images. To overcome the shortcoming, a novel scheme using same-sized range and domain blocks is proposed. Further, a recursive scheme feeding the coding results back to the input during the encoding procedure is used to improve the decoded image quality. Experimental results show our method gives significant improvement over Fisher's FIC.