Idea: write generators as functions rather than directly on specs. Argument: recursion depth. Call generator functions from the spec.

Followed through on a generator namespace with recursion limit. That fixed my StackOverflow. Sample for add and multiply:

(defn add [depth]
  (gen/fmap to-list
            (gen/tuple (gen/return '+) (expression (dec depth)) (expression (dec depth)))))

(defn expression [depth]
  (if-not (pos? depth)
    (number)
    (gen/one-of [(number)
                 (multiply depth)
                 (add depth)])))

Note: Tree depth can also be controlled probabilistically. Make it more probable to take the non-recursive path than the recursive path. Example from the docs:

(gen/frequency [[9 gen/small-integer] [1 (gen/return nil)]])

From reading test.check source, I see that many generators accept a size parameter. I suspect that I could have used that instead of inventing my own depth.