Definition of formula does not preclude recurrence relations.
Evaluation of a formula will always require some form of "turning the crank" whether it involves recurrence or not.
The evaluation of the formula lives in sort of a separate universe then the formula itself. For example the integral or the limit of something represents something as a formula, but sometimes algorithmic evaluation of such things are not possible. A formula can exist EVEN when a algorithm or "turning the crank" evaluation doesn't exist. It's a seperate thing and does not influence the definition of "formula".