Zeckendorf numbers the Clojure way

Question

I'm just getting into Clojure, and I wanted to make sure I am writing code the "Clojure way". The challenge I took on is Zeckendorf numbers (fairly trivial).

(defn fibs-until
 ([n]
 (vec (if (< n 3)
 (range 1 (inc n))
 (concat [1 2] (fibs-until n 1 2)))))
 ([n a b]
 (let [fib (+ a b)]
 (if (> fib n)
 []
 (cons fib (fibs-until n b fib))))))
(defn zeckendorf
 ([n]
 (if (= 0 n) "0" (zeckendorf n (reverse (fibs-until n)))))
 ([n fibs]
 (if (= fibs [])
 ""
 (let [head (first fibs) tail (rest fibs)]
 (if (or (> head n) (= 0 n))
 (str "0" (zeckendorf n tail))
 (str "1" (zeckendorf (- n head) tail)))))))

A few review questions I have:

1. Is there a more "Clojure way" to do this?
2. I noticed that I am repeating the same (overloading-esque) pattern of defining functions that have two arities, and calling out to the second in the first. Is there a better way to do this?
3. I wanted to use [[head & tail] fibs] rather than [head (first fibs) tail (rest fibs)] but I get a stack overflow. Why is this?

Answer 1

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=> (defn fib [a b]
 #_=> (lazy-seq
 #_=> (cons a (fib b (+ a b)))))
#'user/fib
user=> (take 10 (fib 1 1))
(1 1 2 3 5 8 13 21 34 55)
user=> (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=> (take-while #(< % 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.