This article investigates algorithmic learning, in the limit, of corre
ct programs for recursive functions f from both input/output examples
of f and several interesting varieties of approximate additional ( alg
orithmic) information about f, Specifically considered, as such approx
imate additional information about f, are Rose's frequency computation
s for land several natural generalizations from the literature, each g
eneralization involving programs for restricted trees of recursive fun
ctions which have las a branch. Considered as the types of trees are t
hose with bounded variation, bounded width, and bounded rank. For the
case of learning final correct programs for recursive functions, EX-le
arning, where the additional information involves frequency computatio
ns, an insightful and interestingly complex combinatorial characteriza
tion of learning power is presented as a function of the frequency par
ameters. For EX-learning (as well as for BC-learning, where a final se
quence 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 fun
ctions is learnable with that probability. (C) 1997 Academic Press.