The logic obtained by adding the least-fixed-point operator to first- order logic was proposed as a query language by A. Aho and J. Ullman [Proc. 6th ACM Symp. Princ. Program. Lang., 110-120 (1979)] and has been studied, particularly in connection with finite models, by numerous authors. We extend to this logic, and to the logic containing the more powerful iterative-fixed-point operator, the zero-one law proved for first-order logic by Yu. V. Glebskij, D. I. Kogan, M. I. Liogon’kij and V. A. Talanov [Kibernetika 1969, No.2, 17-27 (1969; Zbl 0209.308)] and R. Fagin [J. Symb. Logic 41, 50-58 (1976; Zbl 0341.02044)]. For any sentence \(\phi\) of the extended logic, the proportion of models of \(\phi\) among all structures with universe \(\{\) 1,2,...,n\(\}\) approaches 0 or 1 as n tends to infinity. We also show that the problem of deciding, for any \(\phi\), whether this proportion approaches 1 is complete for exponential time, if we consider only \(\phi\) ’s with a fixed finite vocabulary (or vocabularies of bounded arity) and complete for double-exponential time if \(\phi\) is unrestricted. In addition, we establish some related results.