Recurrent iterated function systems generalize iterated function systems as introduced by the first author and S. Demko [Proc. R. Soc. Lond., Ser. A 399, 243-275 (1985; Zbl 0588.28002)] in that a Markov chain (typically with some zeros in the transition probability matrix) is used to drive a system of maps \(w_ j:\) \(K\to K\), \(j=1,2,...,N\), where K is a complete metric space. It is proved that under “average contractivity”, a convergence and ergodic theorem obtains, which extends the results of the first two authors [Adv. Appl. Probab. 20, No.1, 14-32 (1988; Zbl 0643.60050)]. It is also proved that a Collage Theorem is true, which generalizes the main result of the first and third authors, V. Ervin and J. Lancaster [Proc. Natl. Acad. Sci. USA 83, 1975-1977 (1986; Zbl 0613.28008)] and which broadens the class of images which can be encoded using iterated map techniques. The theory of fractal interpolation functions of the first author [Constructive Approximation 2, 303-329 (1986; Zbl 0606.41005)] is extended, and the fractal dimensions for certain attractors is derived, extending the technique of D. P. Hardin and P. Massopust [Commun. Math. Phys. 105, 455- 460 (1986; Zbl 0605.28006)]. Applications to Julia set theory and to the study of the boundary of IFS attractors are presented.