Zeckendorf numbers the Clojure way
Starting with your last question first, I'm surprised that you don't always get a stack overflow. Clojure does not support tail-call elimination, meaning that purely recursive functions (like both your fibs-until and zeckendorf) are likely to blow up the stack.

There are various reasons why this isn't an issue in practice, first and foremost of which are Clojure's lazy sequences.

Elements of a lazy sequence aren't generated until they're used. Among other things, this means that Clojure can easily handle infinite sequences. So a more idiomatic way to implement Fibonacci would be to return an infinite lazy sequence from which you can simply take however many elements you want. There are lots of ways to implement this, one of which is to simply wrap a recursive implementation with lazy-seq:

user=&gt; (defn fib [a b]
  #_=&gt;   (lazy-seq
  #_=&gt;     (cons a (fib b (+ a b)))))
#'user/fib
user=&gt; (take 10 (fib 1 1))
(1 1 2 3 5 8 13 21 34 55)
user=&gt; (take 20 (fib 1 1))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)


Or, closer to your fib-until function:

user=&gt; (take-while #(&lt; % 100) (fib 1 1))
(1 1 2 3 5 8 13 21 34 55 89)


There are lots of other ways to implement Fibonacci lazily in Clojure.

I'll leave a lazy version of zeckendorf as an exercise ;-)

Regarding your question 2, using multiple arities the way you do is common and nothing to be concerned about IMHO.