The present paper proposes a new perspective on the place of Frege’s work in the history of computability theory, by calling attention to his 1874 Habilitationsschrift. It shows the prominent role played by functional iteration in Frege’s early efforts to provide a general concept of numerical magnitude, attached to an embryonic recursion schema and the use of functions as expressive means. Moreover, a connection is suggested between the iteration theory used and developed by Frege in his treatise and Schröder’s original concern for the mathematical treatment of the problem of the feasibility of algorithmic computation.