I'm trying to wrap my head around recursion with clojure. I'm getting a stack overflow error with the following code, can anyone spot the issue?
(I know this is inefficient but it's strictly for learning purposes)
user=> (defn addall
([] 0)
([& x]
(if (empty? x) 0)
(+ (first x) (addall (rest x)))))
user/addall
user=> (addall 1)
StackOverflowError clojure.lang.ArraySeq.next (ArraySeq.java:78)
It looks like your parenthesization is wrong -- your if needs an else form. I suspect you meant something like:
(defn addall
([] 0)
([& x]
(if (empty? x)
0 ;;; <=== no ')' after 0
(+ (first x) (addall (rest x)))))) ;;; <== extra ')' here
But even with that fixed, your code is still wrong: it assumes that it's called with multiple arguments -- (addall 1 2 3) -- but recurs by passing itself a list -- (addall [2 3]). This results in it getting stuck in a loop that doesn't make any progress, which you can observe by adding a print statement:
(defn addall
([] 0)
([& x]
(print (str "new x: " x "\n"))
(if (empty? x)
0 ;;; <=== no ')' after 0
(+ (first x) (addall (rest x))))))
This actually produced a segfault on my computer!
Also, it has two base cases. I'd suggest this instead:
(defn addall
[xs]
(if (empty? xs)
0
(+ (first xs)
(addall (rest xs)))))
To be called with a vector:
(addall [1 2 3])
Alternatively, if you want to use a variadic function, you'd also need apply:
(defn addall
[& x]
(print (str "new x: " x "\n"))
(if (empty? x)
0
(+ (first x)
(apply addall (rest x))))) ;;; <=== apply addall
That said, you should note that Clojure does not have tail-call optimization, which means that this code would fail with medium-sized inputs. Clojure encourages the use of loop/recur and built-in sequence processing functions instead.
x is bound to (1), the second and subsequent it is bound to (()), which is not empty. An option would be (apply addall (rest x)).
I think this is what you want:
(defn addall ([x] (if (empty? x) 0 (+ (first x) (addall (rest x))))))
as mentioned by Matt Fenwick, you should use loop/recur. A more idiomatic approach is to use reduce:
(reduce + [1 2 3 4 5])
There is a lot of wonderful tools baked in to clojure, and often you don't need things like loop/recur or explicit recursion.
