Transformer-based models struggle to fully learn structural recursion, as they often rely on shortcuts rather than understanding the recursive structure. This paper introduces a framework connecting structural recursion in programming to sequence modeling, analyzing how models handle recursive tasks. The framework includes syntax representation and semantics modeling, enabling analysis of learned behaviors. Models trained on recursive tasks often fail to capture recursion, instead using shortcuts and struggling with edge cases. They also have difficulty learning recursive rules from examples and performing step-by-step reduction. The paper investigates two tasks: binary successor and tree traversal, showing models use non-recursive shortcuts and fail to learn correct semantics. Pre-trained models also struggle with in-context learning. The framework helps understand model behavior, revealing that transformers do not fully encode recursion semantics but instead fit shortcuts. This highlights the need for better methods to handle recursion in sequence models.Transformer-based models struggle to fully learn structural recursion, as they often rely on shortcuts rather than understanding the recursive structure. This paper introduces a framework connecting structural recursion in programming to sequence modeling, analyzing how models handle recursive tasks. The framework includes syntax representation and semantics modeling, enabling analysis of learned behaviors. Models trained on recursive tasks often fail to capture recursion, instead using shortcuts and struggling with edge cases. They also have difficulty learning recursive rules from examples and performing step-by-step reduction. The paper investigates two tasks: binary successor and tree traversal, showing models use non-recursive shortcuts and fail to learn correct semantics. Pre-trained models also struggle with in-context learning. The framework helps understand model behavior, revealing that transformers do not fully encode recursion semantics but instead fit shortcuts. This highlights the need for better methods to handle recursion in sequence models.