# How can I construct a recursive pattern guard?

I am modelling binary trees in Wolfram Language by writing them as three-element lists, like so: binTree = {nodeVal, leftChild, rightChild}.

It does not yet matter what kind of structure nodeVal itself has, but let us assume, for the sake of this problem, that the structure is a list of two integers: nodeValPattern = {_Integer, _Integer}.

Furthermore, leftChild and rightChild can be either {} or have internal nodes of the same shape as binTree itself.

I would like to have a pattern guard for the structure of binTree. The naive attempt does not work:

nodeValPattern = {_Integer, _Integer};
binTreePattern = {nodeValPattern, ({} | binTreePattern), ({} | binTreePattern)};
binTree = {
{{1, 2}, {{2, 3}, {}, {}}, {}},
{{3, 4}, {}, {{4, 5}, {}, {}}},
{}
};
MatchQ[binTree, binTreePattern]


I get the following error:

$RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>  Can you please help? ## 2 Answers Your pattern has itself in its own definition. Mathematica will keep substituting the definition in at each level until it runs out of stack. From this answer about recursive string matching we can see a potential solution: using MatchQ instead of the explicit pattern, since Condition will prevent the recursive part of the pattern from being evaluated when it's defined. Condition // Attributes (* {HoldAll, Protected} *)  Thus we can try this: binTreePattern2 = {nodeValPattern, ({} | (a_ /; MatchQ[a, binTreePattern2])), ({} | (b_ /; MatchQ[b, binTreePattern2]))}; MatchQ[binTree, binTreePattern2] (* False *)  It turns out your tree is not correctly formed! (Look at binTree // TreeForm). Here is an example of a correctly formed tree. binTree2 = {{10, 11}, {{1, 2}, {{2, 3}, {}, {}}, {}}, {{3, 4}, {}, {{4, 5}, {}, {}}}}; MatchQ[binTree2, binTreePattern2] (* True *)  • +1. To be pedantic, while the answer you linked to was the correct answer to that question, the solution to avoid recursion for that question was proposed first in my earlier answer to it. Another nice use of recursive patterns can be found in this answer. I have also used recursive pattern in a very similar setting in the menuTreeValidQ function in this answer on generic nested menu implementation, back in 2009. Commented Feb 27, 2015 at 0:03 • @Leonid Is there not a question at least fairly similar to (5958128) on this site also? I cannot find it now. Edit: Found it: (11045) Commented Feb 27, 2015 at 1:52 • @Mr.Wizard Good point! Actually, I completely forgot about that one. My be, because you beat me there :). Anyway, I think that recursive patterns are a very powerful and under-explored technique. I have used more complex versions of it with great effect several times. May be, at some point one of us (you, WReach or myself) would find some time to write a reference post on this topic. Thanks for the ref. Commented Feb 27, 2015 at 19:15 Referencing How to match expressions with a repeating pattern and How to define a recursive pattern? it is in my opinion superior to use a test function definition, which is easily made a pattern with _?test, to using Condition and MatchQ to avoid an infinite loop. 1. It more easily handles the case should one need to keep parts of the expression unevaluated during testing. 2. It appears to be more efficient in all cases that I have compared. For this problem: test[{{_Integer, _Integer}, {} | _?test, {} | _?test}] := True; _test = False;  Or equivalently you can define the function with pattern sub-parts if you prefer, to improve clarity in large patterns: node = {_Integer, _Integer}; leaf = {} | _?test; test[{node, leaf, leaf}] := True _test = False;  • In either case you could leave out _test = False if test will always be used in _?test but I prefer to make test a complete predicate function. Now a large tree to your specification for the purpose of testing: $RecursionLimit = 10000;
make[] := If[RandomInteger[] == 0, {}, {RandomInteger[9, 2], make[], make[]}];
SeedRandom[835];
bigTree = make[];


Size:

Depth[bigTree]
LeafCount[bigTree]

1642

877496


Speed compared to 2012rcampion's binTreePattern2:

MatchQ[bigTree, binTreePattern2] // RepeatedTiming
MatchQ[bigTree, _?test]          // RepeatedTiming

{0.1790, True}

{0.0764, True}