Examples of recursive predicates

In Stone's Algorithms for Functional Programming, he gives a design pattern for recursively defined predicates, which in Scheme is

(define (check stop? continue? step)
  (rec (checker . arguments) 
    (or (apply stop? arguments) 
        (and (apply continue? arguments) 
             (apply (pipe step checker) arguments)))))

where pipe is the author's function to compose two functions in diagrammatic order, ((pipe f g) x = (g (f x)).

So, for instance, to test whether a function is a power of two, you could define

(define power-of-two? (check (sect = <> 1) even? halve))

where (sect = <> 1) is the author's notation for currying, equivalent to lambda x: x == 1.

Clearly a lot of predicates could be implemented recursively but it would not be useful. And clearly there are some recursive predicates that wouldn't use this pattern, like predicates on trees.

What are some classic predicates that fit this pattern? I guess testing if something is in the Cantor set, but that's almost the same as the above.