Recursion Schemes

A recursion scheme is a way of structuring recursive functional programs.

By and large the term is used in two ways by two distinct communities:

1. In functional programming the term is used to specify some kind of recursive pattern, often called a structural recursion scheme. These are program schemes for functional programs: generic ways of writing recursive programs, essentially "design patterns" for recursive FP. They include lots of colourfully named notions such as catamorphisms, hylomorphisms, and so on.
2. In model checking they refer to Higher-order recursion schemes. This is an abstraction that represents functional programs as a typed grammar.