recursion - How to define a recursive pattern?

I want to translate this recursive syntactic definition into a Mathematica pattern¹:

$$ \mathtt{x}: \begin{cases} \text{Null}\\ \{\textit{integer}, \mathtt{x}\} \end{cases} $$

In other words, all the following Mathematica expressions should match the desired pattern:

Null
{4, Null}
{3, {4, Null}}
{2, {3, {4, Null}}}
{1, {2, {3, {4, Null}}}}

...but none of these should

{}
{Null}
{Null, Null}

{3, 4, Null}

I thought that x:(Null|{_Integer, x}) would do the job, and at least

MatchQ[Null, x : (Null | {_Integer, x})]
(* True *)

but

MatchQ[{4, Null}, x : (Null | {_Integer, x})]
(* False *)

What's the right syntax for the desired pattern?

---

BTW, I could have sworn that I've seen recursive Mathematica patterns of this sort before, and almost certainly in the main Mathematica documentation, but I can't find whatever I think I saw. If my memory is correct, I'd appreciate a pointer to the place in the docs where these are documented. Admittedly, my batting average with the Mathematica documentation is frustratingly low in general, but it is particularly bad when it comes to questions regarding patterns. Therefore I would appreciate any pointers to the documentation that may shed light on this post's question.

---

^{1Those familiar with Lisp will see a formal similarity between this pattern and the canonical Lisp list. But note that here I'm not considering $\text{Null}$ and $\{\}$ as equivalent.}

Answer

What you need is something like this:

patt = Null | (x_ /; MatchQ[x, {_Integer, patt}] )

The trick is to delay the evaluation for the recursive part, until run-time (match attempt), and Condition is one way to do it. So:

MatchQ[#, patt] & /@ {Null, {4, Null}, {3, {4, Null}}, {2, {3, {4, Null}}}, {1, {2, {3, {4, Null}}}}}


(*  {True, True, True, True, True} *)

and

MatchQ[#, patt] & /@ {{}, {Null}, {Null, Null}, {3, 4, Null}}

(* {False, False, False, False} *)

Recursive patterns have been discussed in a number of places, for example: