  This paper investigates the ability of transformer-based models to learn
structural recursion from examples. Recursion is a universal concept in both
natural and formal languages. Structural recursion is central to the
programming language and formal mathematics tasks where symbolic tools
currently excel beyond neural models, such as inferring semantic relations
between datatypes and emulating program behavior. We introduce a general
framework that nicely connects the abstract concepts of structural recursion in
the programming language domain to concrete sequence modeling problems and
learned models' behavior. The framework includes a representation that captures
the general \textit{syntax} of structural recursion, coupled with two different
frameworks for understanding their \textit{semantics} -- one that is more
natural from a programming languages perspective and one that helps bridge that
perspective with a mechanistic understanding of the underlying transformer
architecture.
  With our framework as a powerful conceptual tool, we identify different
issues under various set-ups. The models trained to emulate recursive
computations cannot fully capture the recursion yet instead fit short-cut
algorithms and thus cannot solve certain edge cases that are under-represented
in the training distribution. In addition, it is difficult for state-of-the-art
large language models (LLMs) to mine recursive rules from in-context
demonstrations. Meanwhile, these LLMs fail in interesting ways when emulating
reduction (step-wise computation) of the recursive function.
