CODEWITHSUNDEEP
recursionclojure
Mark
Mark

Reputation: 41175

getting a stack overflow in Clojure function.

Why am I getting a stack overflow in the following Clojure function:

(defn length
  [xs]
  (if ,(not= xs nil)
    (println (+ 1 (length (rest xs))))
    (println 0)))

Upvotes: 3

Views: 236

Answers (2)

Brian Carper
Brian Carper

Reputation: 73006

I think the idiomatic way of doing this is to call seq on your collection. seq on a collection returns nil if the collection is empty.

(defn length [xs]
  (if (seq xs)
      (inc (length (rest xs)))
      0))

This isn't tail-recursive (you aren't using recur and can't here) so this will still overflow the stack on very large collections. 

user> (println (length (range 1000000)))
;; stack overflow

One tail-recursive version would be

(defn length [xs]
  (loop [xs xs
         acc 0]
    (if (seq xs)
        (recur (rest xs) (inc acc))
        acc)))

user> (println (length (range 1000000)))
1000000

This won't overflow the stack even for huge collections but it's still slow. Many Clojure collections implement the Counted interface and the built-in count function returns the length of those collections in constant time.

Upvotes: 10

Andrew
Andrew

Reputation: 85

After the switch to all lazy seqs, rest will never return nil, just an empty list - try this:

(defn length 
   [xs]
   (if (not (empty? xs))
      (println (+ 1 (length (rest xs))))
      (println 0)))

OR this

(defn length
   [xs]
   (if ,(not= xs nil)
      (println (+ 1 (length (next xs))))
      (println 0)))

Upvotes: 4

Related Questions