  Recursive calls over recursive data are useful for generating probability
distributions, and probabilistic programming allows computations over these
distributions to be expressed in a modular and intuitive way. Exact inference
is also useful, but unfortunately, existing probabilistic programming languages
do not perform exact inference on recursive calls over recursive data, forcing
programmers to code many applications manually. We introduce a probabilistic
language in which a wide variety of recursion can be expressed naturally, and
inference carried out exactly. For instance, probabilistic pushdown automata
and their generalizations are easy to express, and polynomial-time parsing
algorithms for them are derived automatically. We eliminate recursive data
types using program transformations related to defunctionalization and
refunctionalization. These transformations are assured correct by a linear type
system, and a successful choice of transformations, if there is one, is
guaranteed to be found by a greedy algorithm.
