This article investigates algorithmic learning, in the limit, of correct programs for recursive functions f from both inputΓoutput examples of f and several interesting varieties of approximate additional (algorithmic) information about f. Specifically considered, as such approximate additional information about f, are Rose's frequency computations for f and several natural generalizations from the literature, each generalization involving programs for restricted trees of recursive functions which have f as a branch. Considered as the types of trees are those with bounded variation, bounded width, and bounded rank. For the case of learning final correct programs for recursive functions, EX-learning, where the additional information involves frequency computations, an insightful and interestingly complex combinatorial characterization of learning power is presented as a function of the frequency parameters. For EX-learning (as well as for BC-learning, where a final sequence of correct programs is learned), for the cases of providing the types of additional information considered in this paper, the maximal probability is determined such that the entire class of recursive functions is learnable with that probability. ] 1997 Academic Press EX-style learning [9] requires of each function in a class learned that, in the limit, a single correct program be found.