Adjoin-set for an ordered set representation
Calling element-of-set? from adjoin-set introduces unnecessary redundancy.  One may incorporate this test within the adjoin-set function (in your case, rec should be the main body of your function, with an = test added):

(define (adjoin-set x set)
  (cond
    ((null? set) (cons x set))
    ((= x (car set)) set)
    ((&lt; x (car set)) (cons x set))
    (else (cons (car set) (adjoin-set x (cdr set))))))


This function performs fewer steps since it does not call element-of-set?.  However, its complexity is still O(n), which is the same as your implementation's complexity, as well as the complexity of element-of-set?.